二叉堆

Posted on | Post modified:
Words count in article: 809 | Reading time ≈ 3

任务

实现一个堆，实现插入、寻找最小值、任意修改元素、删除任意元素。

说明

　由于堆是完全二叉树(或者说类完全二叉树，关于二叉堆，详情请见：binary heap)。我们使用小标从1开始的数组来表示树，1代表根节点，对于每个节点i，它的左节点为 i 2，右节点为 i 2 + 1，父节点为 i / 2；
　我们使用数组heap[]来记录堆中的元素。使用id[]和pos[]来分别记录修改操作中堆中位置为i的元素是第几个插入的和删除操作中第i个插入的元素在堆中的位置。
实现堆核心函数为up(i)和down(i)，up(i)使堆中的节点不断“上升”，相反，down(i)使堆中的节点不断“下沉”。
　在插入一个值value时，我们将它加入堆的最底层，然后通过比较确定是否“上升”；删除元素时，我们将该元素修改为负无穷大，然后使其上浮到根，最后删除堆顶元素。

注：堆顶元素(根节点)小标从0开始也是一样的，对于每个节点i，它的左节点为i 2 + 1, 右节点为 i 2 + 2,父节点为 （i - 1） / 2。

接口

  • 结构体： BinaryHeap
  • 成员变量：
    　　　　int n　　　　　　　堆当前元素个数
    　　　　int counter　　　　 加入堆中的元素个数
    　　　　int heap[]　　　　　堆中的元素
    　　　　int id[]　　　　　 　堆中位置为i的元素时第几个插入堆的
    　　　　int pos　　　　　　 第i个插入堆中的元素在堆中的位置
  • 成员函数：
    　　　　BinaryHeap();　　　　　　　　　　　　 　构造空堆
    　　　　BinaryHeap(int array[], int offset);　　　　 将数组中的元素按顺序插入和构造的堆
    　　　　void push(int v);　　　　　　　　　　　　插入元素
    　　　　int pop();　　　　　　　　　　　　　　　删除栈顶元素
    　　　　int get();　　　　　　　　　　　　　　 　获取第i插入堆中的元素值
    　　　　void modify();　　　　　　　　　　　　　修改第i个元素为value
    　　　　void delet(int i);　　　　　　　

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
const int MAXSIZE = 100000;  // the size of binary heap
struct BinaryHeap {
  int heap[MAXSIZE], id[MAXSIZE], pos[MAXSIZE], n, counter;
  BinaryHeap(): n(0), counter(0) {}
  BinaryHeap(int array[], int offset): n(0), counter(0) {
    for(int i = 0; i < offset; ++i){
      heap[++n] = array[i];
      id[n] = pos[n] = n;
    }
    for(int i = n/2; i>= 1; --i) {
      down(i);
    }
  }

  void push(int v) {
    heap[++n] = v;
    id[n] = ++counter;
    pos[id[n]] = n;
    up(n);
  }

  int top() {
    return heap[1];
  }

  int pop() {
    swap(heap[1],heap[n]);
    swap(id[1],id[n--]);
    pos[id[1]] = 1;
    down(1);
    return id[n+1];
  }

  void swap(int num1, int num2){
    int temp = 0;
    num1 = temp;
    num1 = num2;
    num2 = temp;
  }

  int get(int i) {
    return heap[pos[i]];
  }

  void modify(int i, int value) {
    heap[pos[i]] = value;
    down(pos[i]);
    up(pos[i]);
  }

  void delet(int i) {
    heap[pos[i]] = INT_MIN;
    up(pos[i]);
    pop();
  }

  void up(int i) {
    int x = heap[i], y = id[i];
    for(int j = i/2; j >= 1; j /= 2){
      if(heap[j] > x){
        heap[i] = heap[j];
        id[i] = id[j];
        pos[id[i]] = i;
        i = j;
      }else{
        break;
      }
    }
    heap[i] = x;
    id[i] = y;
    pos[y] = i;
  }

  void down(int i) {
    int x = heap[i], y = id[i];
    for(int j = i * 2; j <= n; j *= 2) {
      j += j < n && heap[j] > heap[j + 1];
      if(heap[j] < x){
        heap[i] = heap[j];
        id[i] = id[j];
        pos[id[i]] = i;
        i = j;
      }else{
        break;
      }
    }
    heap[i] = x;
    id[i] = y;
    pos[y] = i;
  }

  bool empty() {
    return n == 0;
  }

  int size() {
    return n;
  }
};

有问题？发送 issues 给我~

0%