最小堆_最小堆算法

概念

堆是一个用数组表示的完全二叉树，并满足以下两个特性：
1）父节点的键值总是大于或等于（小于等于）其子树上的任意结点
2）每个结点的左子树和右子树都是个堆。
如果父节点的键值总是大于等于任何一个子节点的键值，那么这时称之为最大堆或者大顶堆。反之，如果父节点的键值总是小于等于任何一个子节点的键值，那么这时称之为最小堆或者小顶堆。

---

插入操作

算法如下：
1）如果堆已满则不能插入
1）否则，把需要插入的值x插入到数组最后然后进行调整
2）从最后一个结点的父节点开始循环，如果父节点大于（小于）x，把父节点与x进行对换。
最大堆算法如下（最小堆与之类似，不在此赘述）：

//最大堆的插入操作 
bool Insert(int num){
	//最大堆已满则无法插入 
	if(this->IsFull()){
		return false;
	}
	//保存最后一个元素的位置
	int i = ++size; 
	//从最后一个元素的父节点开始进行过滤
	//如果父节点小于num，那么把父节点下移 
	//data[0]控制哨兵元素，它不小于最大堆中最大元素，控制循环结束 
	for(; this->data[i/2] < num ; i /= 2){
		this->data[i] = this->data[i/2];
	}
	this->data[i] = num;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

删除操作

算法如下：
1）如果堆为空，那么不能进行删除
2）否则，首先保存根节点的键值，之后用最后一个结点来代替根节点，对堆进行相应的调整使之称为最大堆或者最小堆。
3）遍历整个堆，找到左右孩子中的最大值（最小值），之后与根节点进行比较，如果根结点小于（大于）左右孩子中则把根结点下移。如果根结点大于等于（小于等于）则跳出循环。

//把data[n]为根的子堆调整为最大堆
void Predown(int n){
	//保存下标为n的元素
	int x = this->data[n];
	int parent,child = 1;
	//用最后一个元素来替代第一个最大值 
	for(parent = n ; parent*2 <= this->size ; parent = child){
		//child指向当前结点的左孩子 
		child = parent*2;
		//左孩子的下标不等于最大堆容量，则说明有右孩子
		//右孩子的键值如果父节点，那么child指向右孩子，否则仍指向左孩子 
		if(child != this->size && this->data[child] < this->data[child+1]){
			child++;//选择左右孩子中最大值 
		}
		if(x >= this->data[child]){//找到了合适的位置 
			break;
		}else{//把孩子上移
			this->data[parent] = this->data[child];
		}
	}
	this->data[parent] = x; 
}

//最大堆的删除最大值操作
int DeleteMax(){
	//最大堆是空时 
	if(this->IsEmpty()){
		return MaxData;
	} 
	int max = this->data[1];
	this->data[1] = this->data[size];
	//最大堆规模减一 
	this->size--;
	//然后把最后一个元素为根结点进行调整为最大堆 
	this->Predown(1);
	return max; 
}
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

---

建堆操作

建堆操作有以下两种方式：
1）通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中，其时间代价最大为O(NlogN)
2）线性时间复杂度下建堆：
a）将N个元素依次存入数组里，满足完全二叉树的顺序 储性质
b）调整各个结点的位置，以满足最大堆的有序性
通常采取第二种方式建堆
算法如下：
1）首先把数据输入到堆中
2）从倒数第一个有子节点的父节点开始调整，把这个父节点为根节点的子树调整为堆，直至到根节点

//把data[n]为根的子堆调整为最大堆
void Predown(int n){
	//保存下标为n的元素
	int x = this->data[n];
	int parent,child = 1;
	//用最后一个元素来替代第一个最大值 
	for(parent = n ; parent*2 <= this->size ; parent = child){
		//child指向当前结点的左孩子 
		child = parent*2;
		//左孩子的下标不等于最大堆容量，则说明有右孩子
		//右孩子的键值如果父节点，那么child指向右孩子，否则仍指向左孩子 
		if(child != this->size && this->data[child] < this->data[child+1]){
			child++;//选择左右孩子中最大值 
		}
		if(x >= this->data[child]){//找到了合适的位置 
			break;
		}else{//把孩子上移
			this->data[parent] = this->data[child];
		}
	}
	this->data[parent] = x; 
}

//最大堆的建立函数 
void Create(int* data ,int n){
	//把数据导入最大堆 
	for(int i = 0 ; i < n ; i++){
		this->data[++size] = data[i];
	}
	//从最后一个结点的父节点开始逐步之为根结点的子堆调整为最大堆 
	for(int i = this->size/2 ; i >= 1 ; i--){
		this->Predown(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

---

具体例子

全部代码如下：

#include <iostream>
using namespace std;

//作为最大堆的第0个元素，以之为哨兵 
const int MaxData = 1000000;

class MaxHeap{
	private:
		int* data;			//存储数据的数组 
		int size;			//当前规模 
		int capacity;		//最大容量
	public:
		//最大堆的构造函数 
		MaxHeap(int MaxSize){
			this->data = new int[MaxSize];
			this->size = 0;
			this->capacity = MaxSize;
			this->data[0] = MaxData;
		}
		
		//把data[n]为根的子堆调整为最大堆
		void Predown(int n){
			//保存下标为n的元素
			int x = this->data[n];
			int parent,child;
			//用最后一个元素来替代第一个最大值 
			for(parent = n ; parent*2 <= this->size ; parent = child){
				//child指向当前结点的左孩子 
				child = parent*2;
				//左孩子的下标不等于最大堆容量，则说明有右孩子
				//右孩子的键值如果父节点，那么child指向右孩子，否则仍指向左孩子 
				if((child != this->size) && this->data[child] < this->data[child+1]){
					child++;//选择左右孩子中最大值 
				}
				if(x >= this->data[child]){//找到了合适的位置 
					break;
				}else{//把孩子上移
					this->data[parent] = this->data[child];
				}
			}
			this->data[parent] = x; 
		}
		
		//最大堆的建立函数 
		void Create(int* data ,int n){
			//把数据导入最大堆 
			for(int i = 0 ; i < n ; i++){
				this->data[++size] = data[i];
			}
			//从最后一个结点的父节点开始逐步之为根结点的子堆调整为最大堆 
			for(int i = this->size/2 ; i > 0 ; i--){
				this->Predown(i); 
			}
		} 
		
		//判断最大堆是否已满
		bool IsFull(){
			return this->size == this->capacity;
		} 
		
		bool IsEmpty(){
			return this->size == 0;
		}
		
		//最大堆的插入操作 
		bool Insert(int num){
			//最大堆已满则无法插入 
			if(this->IsFull()){
				return false;
			}
			//保存最后一个元素的位置
			int i = ++size; 
			//从最后一个元素的父节点开始进行过滤
			//如果父节点小于num，那么把父节点下移 
			//data[0]控制哨兵元素，它不小于最大堆中最大元素，控制循环结束 
			for(; this->data[i/2] < num ; i /= 2){
				this->data[i] = this->data[i/2];
			}
			this->data[i] = num;
			return true;
		}
		
		//最大堆的删除最大值操作
		int DeleteMax(){
			//最大堆是空时 
			if(this->IsEmpty()){
				return MaxData;
			} 
			int max = this->data[1];
			this->data[1] = this->data[size];
			//最大堆规模减一 
			this->size--;
			//然后把第一个元素为根结点进行调整为最大堆 
			this->Predown(1);
			return max; 
		}
		
		//打印最大堆
		void Print(){
			for(int i = 1 ; i <= this->size ; i++){
				cout<<this->data[i]<<" ";
			}
		} 
};

int main()
{
	cout<<"请输入最大堆的最大容量："<<endl;
	int capacity;
	cin>>capacity;
	MaxHeap maxheap(capacity); 
	cout<<"请输入初始化最大堆的元素个数:"<<endl;
	int size,*data;
	cin>>size;
	data = new int[size];
	cout<<"请初始化元素:"<<endl;
	for(int i = 0 ; i < size ; i++){
		cin>>data[i];
	}
	maxheap.Create(data,size);
	cout<<"最大堆为:"<<endl;
	maxheap.Print();
	cout<<endl;
	
	//在最大堆中插入元素
	cout<<"请输入要插入的元素："<<endl;
	int num;
	cin>>num;
	maxheap.Insert(num);
	cout<<"最大堆为:"<<endl;
	maxheap.Print(); 
	cout<<endl;
	
	cout<<"进行删除操作"<<endl;
	int x = maxheap.DeleteMax();
	cout<<"删除元素为："<<x<<endl;
	cout<<"最大堆为:"<<endl;
	maxheap.Print();
	
	return 0;
 } 
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

截图如下：