一、基本知识
- 初始化堆：按照完全二叉树的结构，从上到下、从左到右依次放入元素，然后可以认为所有的叶子结点已经符合大（小）顶堆，接下来，从下到上、从右到左依次调整所有非叶子结点，直至满足大（小）顶堆的要求。
- 堆的插入：每次插入一个结点，只需调整插入结点与其父结点的位置，以及由于与父结点的调整带来的其它不满足堆定义的结点。
- 堆的存储：双亲数组表示法，索引从0开始。结点i的父结点为(i-1)/2;左孩子为2*i+1; 结点右孩子为2*i+2;
- 堆的删除：每次只能删除根节点。首先最后一个元素和根节点交换，删除根节点，重新按照第一步调整堆结构。
基本算法（小顶堆）：
#include <iostream>
#include <algorithm>
using namespace std;
//依次插入元素，建立堆，从下到上进行堆调整
void minHeapFixUp(int * a, int i)
{
int insertValue = a[i];
int parentIndex = (i-1)/2;
while(parentIndex >= 0 && i != 0)
{
if(a[parentIndex] <= insertValue)
break;
a[i] = a[parentIndex];
i = parentIndex;
parentIndex = (i-1)/2;
}
a[i] = insertValue;
}
//从某个结点向下调整堆
void minHeapFixDown(int * a, int i, int n)
{
int rootValue = a[i];
int childIndex = 2*i + 1;
while(childIndex < n)
{
if(childIndex + 1 < n && a[childIndex] > a[childIndex+1])
childIndex++;
if(rootValue <= a[childIndex])
break;
a[i] = a[childIndex];
i = childIndex;
childIndex = 2*i + 1;
}
a[i] = rootValue;
}
//删除元素
void minHeapDelete(int * a, int n)
{
swap(a[0], a[n-1]);
minHeapFixDown(a, 0, n-1);
}
int main()
{
int a[9] = {7,1,2,3,6,5,8,9,4};
int n = sizeof(a)/sizeof(int);
//依次插入元素，建立堆
//for(int i = 0; i < 9; ++i)
//minHeapFixUp(a, i);
//堆化数组
for(int i = (n-1)/2; i >= 0; --i)
{
minHeapFixDown(a, i, n);
}
for(int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
//堆排序
for(int i = n-1; i >= 1; --i)
{
swap(a[0], a[i]);
minHeapFixDown(a, 0, i);
}
for(int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
二、示例
题意：寻找最小的k个数
算法思想：由于是找出最小的k个数，k个数不必有序，剩下的n-k个数也不必有序，因此：
- 使用容量为k的最大堆存储最先遍历到的k个元素
- 依次遍历剩下的n-k个元素，与大顶堆的根结点进行比较，如果a[i] < a[0],替换，否则，忽略
建堆的时间复杂度O(k)，更新堆的复杂度是O((n-k)logk)，因此最坏情况下的时间复杂度是O(nlogk)
#include <iostream>
#include <algorithm>
using namespace std;
void minHeapFixUp(int * a, int i)
{
int insertValue = a[i];
int parentIndex = (i-1)/2;
while(parentIndex >= 0 && i != 0)
{
if(a[parentIndex] >= insertValue)
break;
a[i] = a[parentIndex];
i = parentIndex;
parentIndex = (i-1)/2;
}
a[i] = insertValue;
}
//从某个结点向下调整堆
void minHeapFixDown(int * a, int i, int n)
{
int rootValue = a[i];
int childIndex = 2*i + 1;
while(childIndex < n)
{
if(childIndex + 1 < n && a[childIndex] < a[childIndex+1])
childIndex++;
if(rootValue >= a[childIndex])
break;
a[i] = a[childIndex];
i = childIndex;
childIndex = 2*i + 1;
}
a[i] = rootValue;
}
void getKs(int * a, int k, int n)
{
for(int i = 0; i < k; ++i)
minHeapFixUp(a, i);
for(int i = k; i < n; ++i)
{
if(a[i] < a[0])
{
a[0] = a[i];
minHeapFixDown(a, 0, k);
}
}
for(int i = 0; i < k; ++i)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int a[9] = {7,1,2,3,6,5,8,9,4};
int n = sizeof(a)/sizeof(int);
//找出最小的k个元素
getKs(a, 3, n);
return 0;
}
三、使用STL模板堆算法
主要函数：
- make_heap(first_pointer, end_pointer, compare_function) 没有比较函数时，默认为大顶堆，函数功能：将一段的数组或向量初始化堆结构
- push_heap(first_pointer, end_pointer, compare_function) 在[first, last-1]是堆结构的前提下，将之后的元素加入堆
- pop_heap(first_pointer, end_pointer, compare_function) 将first和last元素交换，调整[first, last-1]为堆结构
- sort_heap(first_pointer, end_pointer, compare_function) 将符合堆结构的一段数组或向量排序（前提必须是堆）
- is_heap(first_pointer, end_pointer, compare_function) 判断一段数组或向量是否是堆，是返回1
#include <iostream>
#include <algorithm>
using namespace std;
void print(int * a, int n)
{
for(int i = 0; i < n; ++i)
cout << *(a+i) << " ";
cout << endl;
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int a[20] = {2,1,3,4,5,6,9,8,7,0};
//默认为大顶堆
make_heap(a, a+10, cmp);
print(a, 10);
//push_heap并不是添加一个元素，而是，假设[first, last-1]已经是一个堆，再把堆中的新元素加进来，组成一个新的堆
a[10] = 11; a[11] = 12; a[12] = -1;
push_heap(a, a+13, cmp);
print(a, 13);
//pop_heap并不是弹出一个元素，而是，将first与last元素交换，然后将[first, last-1]组成一个新的堆
pop_heap(a, a+11, cmp);
print(a, 11);
//sort_heap对一个堆进行排序,前提必须是堆
sort_heap(a, a+10, cmp);
print(a, 10);
return 0;
}
网友评论