今天我们来实现一个大顶堆，所谓大顶堆，即根节点的值大于等于其孩子节点的值。废话少絮，直接开始。
堆是一个完全二叉树，很适合用顺序结构来实现，这里我们选择数组。用数组实现堆时，我们不使用数组的0号位置，用1号位置来存放堆顶（当然也可以使用0号位置来存放堆顶，只是下面的性质要改变），此时，有两个很重要的性质我们需要知道，如下：
- N号元素的父节点的位置为N/2。
- N号元素的左孩子的位置是2N，右孩子的位置是2N+1。
知道这些之后，我们就可以开始实现堆啦（撒花，终于开始了）。
我们从最基础的开始，对于一个堆来说，它需要一个数组来存放数据，需要一个变量来记录元素的个数，如下是一个基础的大顶堆类：
template<typename Item>
class MaxHeap{
private:
Item* data; //数据
int count; //数据个数
int capacity; //容量
public:
MaxHeap(int capacity) { //构造函数分配空间
data = new Item(capacity+1);
count=0;
this->capacity = capacity;
}
~MaxHeap() { //析构函数释放内存
delete[] data;
}
int size() { //返回堆元素的个数
return count;
}
bool isEmpty() { //判断对是否为空
return count == 0;
}
};
data用来存放数据，由于不知道具体有多少数据，所以我们使用指针类型；count用来表示实际的元素个数；capacity表示最多能存放多少数据。用户不需要直接访问这些数据，所以我们将其作为私有类型。
然后我们提供一个构造函数，参数是堆的容量，我们在构造函数里为堆分配内存，并设置实际元素的个数和容量的大小。既然分配了内存，相应的，析构函数里就需要释放这些内存。
除此之外，我们还提供了两个工具函数，分别返回堆内元素的个数和判断堆是否为空。
现在我们有了一个基础的堆，并且可以给这个堆分配空间了：
MaxHeap<int> maxheap = MaxHeap<int>(100);
有了空间之后，我们怎么往这个空间里添加元素呢？我们需要提供一个插入函数：在不超过容量限制的情况下，每次将新元素放置在data的最后，此时，新元素可能不满足大顶堆的性质，我们比较新元素与其父元素之间的大小关系，调整新元素与父元素的位置，直到整个堆满足大顶堆的要求。
假设已经有了调整新元素与父元素之间位置的函数shiftUp，那么，插入函数就很简单了：
void insert(Item item) { //向堆中插入一个元素
assert(count+1 <= capacity); //首先判断空间是否够用
data[count+1] = item; //将新元素放到数组的最后
count++; //元素个数加1
shiftUp(count); //对堆进行调整
}
重点是shiftUp函数，由于用户不需要直接调用这个函数，所以我们将其作为私有的函数：
void shiftUp(int k) { //调整堆的第k个元素
while(k > 1 && data[k/2] < data[k]) { //判断第k个元素是否比其父元素大
swap(data[k/2], data[k]); //交换
k /= 2;
}
}
学会了插入元素，下面我们要学习怎么从堆里删除一个元素了：我们每次只能删除堆顶的元素，然后将最后一个元素交换到堆顶，此时新的堆顶元素可能不满足堆的性质，所以我们比较堆顶与其孩子之间的大小关系，并调整其位置，直到整个堆合法。
仍然假设已经有了调整新堆顶与孩子之间位置的函数shiftDown，那么，删除函数也很简单：
Item getMax() {
assert(count > 0);
Item res = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return res;
}
shiftDown函数的实现如下：首先判断该元素是否有孩子节点，如果该元素还有右孩子，则比较两个孩子的大小，找到较大的孩子，然后比较该元素与较大的孩子节点的大小，如果当前元素小于较大的孩子节点，则交换两者的位置。然后，交换后的元素再次与其孩子进行比较，直到满足堆的条件。
void shiftDown(int k) {
while(2*k <= count) {
int j = 2*k;
if(j+1 <= count && data[j] < data[j+1]) {
j += 1;
}
if(data[k] >= data[j]) {
break;
}
swap(data[k], data[j]);
k = j;
}
}
现在我们的对已经基本可以使用了。为了测试方便，我们还可以增加一个打印堆内元素的工具函数：
void printData() { //打印堆中的元素
for(int i = 1; i <= count; i++) {
cout<<data[i]<<" ";
}
}
下面我们可以测试一下了：
int main() {
MaxHeap<int> maxheap = MaxHeap<int>(100);//构造一个堆
srand(time(NULL));
for(int i = 0; i < 15; i++) {//给堆内的元素赋随机值
maxheap.insert(rand() % 100);
}
maxheap.printData(); //打印堆内的数据
cout<<maxheap.size()<<endl;//打印堆元素的个数
while(!maxheap.isEmpty()) { //从大到小依次输出堆内的每一个元素
cout<<maxheap.getMax()<<endl;
}
return 1;
}
我们的堆已经可以工作了，是不是很开心呀！也许不会说：
我不想每次都构造一个空的堆，然后再一个一个的插入元素啊，我想要直接用数组构造一个堆啊
聪明的你，这种想法简直太棒了。一个一个插入元素的做法，时间复杂度是O(nlgn)，如果直接使用数组来构造堆，时间复杂度可以为O(lgN)哟，你说你是不是很棒！
好了，现在我们开始写这个构造函数吧。思路也很简单：我们直接将数组元素作为堆的元素，然后从第一个非叶节点的元素（第一个有孩子的元素）开始（我们可以认为每个叶节点都是大顶堆），一直到堆顶元素，如果某个元素不满足堆的性质，我们就调整其与孩子节点的位置。
MaxHeap(Item a[], int n) { //使用数组构造堆
data = new Item(n+1); //初始化堆
capacity = n;
for(int i = 0; i < n; i++) {
data[i+1] = a[i];
}
count = n;
for(int i = count/2; i >= 1; i--) {//调整堆
shiftDown(i);
}
}
我们现在已经写完自己的堆啦！大顶堆类的完整代码如下：
template<typename Item>
class MaxHeap{
private:
Item* data; //数据
int count; //数据个数
int capacity; //容量
void shiftUp(int k) { //调整堆的第k个元素
while(k > 1 && data[k/2] < data[k]) { //判断第k个元素是否比其父元素大
swap(data[k/2], data[k]); //交换
k /= 2;
}
}
void shiftDown(int k) {
while(2*k <= count) {
int j = 2*k;
if(j+1 <= count && data[j] < data[j+1]) {
j += 1;
}
if(data[k] >= data[j]) {
break;
}
swap(data[k], data[j]);
k = j;
}
}
public:
MaxHeap(int capacity) { //构造函数分配空间
data = new Item(capacity+1);
count=0;
this->capacity = capacity;
}
MaxHeap(Item a[], int n) { //使用数组构造堆
data = new Item(n+1);
capacity = n;
for(int i = 0; i < n; i++) {
data[i+1] = a[i];
}
count = n;
for(int i = count/2; i >= 1; i--) {
shiftDown(i);
}
}
~MaxHeap() { //析构函数释放内存
delete[] data;
}
int size() { //返回堆元素的个数
return count;
}
bool isEmpty() { //判断对是否为空
return count == 0;
}
void insert(Item item) { //向堆中插入一个元素
assert(count+1 <= capacity); //首先判断空间是否够用
data[count+1] = item; //将新元素放到数组的最后
count++; //元素个数加1
shiftUp(count); //对堆进行调整
}
Item getMax() {
assert(count > 0);
Item res = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return res;
}
void printData() { //打印堆中的元素
for(int i = 1; i <= count; i++) {
cout<<data[i]<<" ";
}
}
};
参考简书算法课，侵删。
网友评论