二叉堆简述

Posted on | In

简述

对于堆，我个人的理解就是一种优先队列，从队列中取元素的时候总是取出最大（或最小）的元素。二叉堆是一种堆的一种实现形式，是一棵完全二叉树。对于二叉堆，我们显然可以分成两类：大根堆和小根堆，表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质，即：对于任意一个节点，他一定不大于他的父亲，而且不小于他的两个儿子。小根堆反之。

实现功能

以$O(n)$的时间建树，并以$O(logn)$的复杂度实现插入、寻找最小（或最大）值，修改元素，删除元素。

实现思路（小根堆）

我们用一个数组来储存数据，下标从1开始，对于第$i$个元素，他的左儿子为$i2$，他的右儿子为$i2+1$，当然对于非根节点，他的父亲就是$i/2$。在这里，这个数组用$heap[]$表示。

同时，我们用数组$id[i]$数组来表示第(i)个元素是第几个插入的，用$pos[i]$来表示第$i$个元素是第几个插入的（很明显有$id[pos[i]]=i$）。当然，根据实际情况，这两个东西可以不要。

这里要用到的最重要的两个函数是$up(i)$和$down(i)$函数， $up(i)$函数是将第$i$个元素上移，如果他比他的父亲大，就和他的父亲交换位置，即维护他比他父亲小的性质。$down(i)$函数类似，只是比较的是两个儿子中较小的那个。

接下来是算法的核心：

  • 当加入一个元素时，我们把他加入到堆的底部，即heap数组的末尾，然后调用$up(i)$函数将其上移到合适位置。
  • 当修改一个元素时，只要直接修改，然后分别调用$down(i)$函数和$up(i)$函数找到他适合的位置。
  • 当删除堆顶元素的时候，我们只要把他和最后一个元素交换位置（这样只需要将数组大小减一就可以删掉他），然后用$down(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
100
101
102
#include<algorithm>
using namespace std;
const int MAXSIZE = 100000;
struct Heap{
	int heap[MAXSIZE];//记录堆的元素,下标从1开始
	int n;//堆中元素的个数
	int counter;//加入到堆中的元素的个数（考虑到被删除的元素）
	int id[MAXSIZE];//第i个元素是第几个加入的
	int pos[MAXSIZE];//第i个加入的元素的位置
	Heap();//一个空的Heap
	Heap(int *, int n);//用一个数组初始化Heap,数组下标从0开始
	void push(int v);//添加元素v
	void change(int i, int value);//把第i个加进去的元素修改为value
	void pop();//删掉堆顶
	void erase(int i);//删除第i个加进去的元素
	void up(int i);//将数组中第i个元素上移
	void down(int i);//将数组中第i个元素下移
	int top();//返回堆顶元素
};

Heap::Heap(){
	n = counter = 0;
}

Heap::Heap(int a[], int n){
	n = counter = 0;
	for (int i = 0; i < n; i++){
		heap[++n] = a[i];
		id[n] = pos[n] = n;
	}
	for (int i = n / 2; i >= 1; i--){
		down(i);
	}
}

void Heap::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 Heap::down(int i){
	int x = heap[i], y = id[i];
	for (int j = i * 2; j <= n; j *= 2){
		if (j<n&&heap[j]>heap[j + 1])
			j++;
		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 Heap::push(int v){
	heap[++n] = v;
	id[n] = ++counter;
	pos[counter] = n;
	up(n);
}

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

void Heap::pop(){
	swap(heap[1], heap[n]);
	swap(id[1], id[n--]);
	pos[id[1]] = 1;
	down(1);
}

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

void Heap::erase(int i){
	heap[pos[i]] = heap[1] - 1;
	up(pos[i]);
	pop();
}