最大堆和最小堆是一种常见的数据结构，其主要用途是实现优先队列。堆的本质是完全二叉树，可以通过数组方式顺序存储；每当堆发生变换时，需要通过节点的上浮和下沉操作，来保证堆的节点之前的严格大小关系。
C++实现
以下代码是最大/最小堆的C++实现。通过观察发现，最大堆和最小堆的节点调整操作都是一样的，差异在于节点之间的大小比较判断，所以为了尽可能复用代码，采用继承方式实现：堆的基本操作在基类中实现，由最大堆和最小堆的子类继承，不必重复实现；而将节点比较操作定义为纯虚函数，最大最小堆各自实现自己判断节点大小顺序的版本。
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 <vector>
class BinaryHeap {
public:
BinaryHeap(const std::vector<int>& data);
virtual ~BinaryHeap() {}
void buildHeap();
void insertNode(int node);
int deleteNode();
void printData();
private:
void upAdjust();
void downAdjust(unsigned parentIndex);
virtual bool compare(int parent, int child) = 0;
private:
std::vector<int> array;
};
class MaxBinaryHeap : public BinaryHeap {
public:
MaxBinaryHeap(const std::vector<int>& data);
~MaxBinaryHeap() {}
bool compare(int parent, int child);
};
class MinBinaryHeap : public BinaryHeap {
public:
MinBinaryHeap(const std::vector<int>& data);
~MinBinaryHeap() {}
bool compare(int parent, int child);
};
|
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
| #include <iostream>
#include "BinaryHeap.h"
using namespace std;
BinaryHeap::BinaryHeap(const vector<int>& data)
: array(data) {
}
void BinaryHeap::upAdjust() {
unsigned childIndex = array.size()-1;
unsigned parentIndex = (childIndex-1)/2;
int temp = array.back();
while (childIndex > 0 && compare(array[parentIndex], temp)) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex-1)/2;
}
array[childIndex] = temp;
}
void BinaryHeap::downAdjust(unsigned parentIndex) {
int temp = array[parentIndex];
unsigned childIndex = 2*parentIndex+1;
while(childIndex < array.size()) {
if (childIndex+1 < array.size() &&
compare(array[childIndex], array[childIndex+1])) {
childIndex++;
}
if (compare(array[childIndex], temp))
break;
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2*parentIndex+1;
}
array[parentIndex] = temp;
}
void BinaryHeap::buildHeap() {
for (int i=(array.size()-2)/2; i>=0; --i) {
downAdjust(static_cast<unsigned>(i));
}
}
void BinaryHeap::insertNode(int node) {
array.push_back(node);
upAdjust();
}
int BinaryHeap::deleteNode() {
int retval = array.front();
array.front() = array.back();
array.pop_back();
downAdjust(0);
return retval;
}
void BinaryHeap::printData() {
for (vector<int>::iterator it=array.begin(); it!=array.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
MaxBinaryHeap::MaxBinaryHeap(const std::vector<int>& data)
: BinaryHeap(data)
{}
bool MaxBinaryHeap::compare(int parent, int child) {
if (parent < child)
return true;
else
return false;
}
MinBinaryHeap::MinBinaryHeap(const std::vector<int>& data)
: BinaryHeap(data)
{}
bool MinBinaryHeap::compare(int parent, int child) {
if (parent > child)
return true;
else
return false;
}
int main() {
vector<int> test={1,3,2,6,5,7,8,9};
cout << "-------Max Heap------" << endl;
BinaryHeap *maxHeap = new MaxBinaryHeap(test);
maxHeap->buildHeap();
cout << "Build heap: ";
maxHeap->printData();
maxHeap->insertNode(10);
cout << "Insert node 10: ";
maxHeap->printData();
for (unsigned i=0; i<test.size();i++) {
cout << "Deleted: " << maxHeap->deleteNode() << endl;
}
maxHeap->printData();
cout << "-------Min Heap------" << endl;
BinaryHeap *minHeap = new MinBinaryHeap(test);
minHeap->buildHeap();
cout << "Build heap: ";
minHeap->printData();
minHeap->insertNode(0);
cout << "Insert node 0: ";
minHeap->printData();
for (unsigned i=0; i<test.size();i++) {
cout << "Deleted: " << minHeap->deleteNode() << endl;
}
minHeap->printData();
delete maxHeap;
delete minHeap;
return 0;
}
|
1
| g++ -std=c++11 -Wall -g -o binary_heap ./BinaryHeap.cpp
|