0%

最大堆最小堆和优先队列

最大堆和最小堆是一种常见的数据结构,其主要用途是实现优先队列。堆的本质是完全二叉树,可以通过数组方式顺序存储;每当堆发生变换时,需要通过节点的上浮和下沉操作,来保证堆的节点之前的严格大小关系。

C++实现

以下代码是最大/最小堆的C++实现。通过观察发现,最大堆和最小堆的节点调整操作都是一样的,差异在于节点之间的大小比较判断,所以为了尽可能复用代码,采用继承方式实现:堆的基本操作在基类中实现,由最大堆和最小堆的子类继承,不必重复实现;而将节点比较操作定义为纯虚函数,最大最小堆各自实现自己判断节点大小顺序的版本。

  • 头文件BinaryHeap.h
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);
};
  • 类实现BinaryHeap.cpp
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