二叉堆

任务

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

说明

 由于堆是完全二叉树(或者说类完全二叉树,关于二叉堆,详情请见: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;
}
};

~

感谢你对我的支持 让我继续努力分享有用的技术和知识点.