二叉堆的实现 && 海量数据中堆的应用
本帖最后由 Knuth学徒 于 2011-2-7 11:04 编辑首先介绍下什么是堆，这里的堆指的是一种数据结构, 它的用途很广泛，包括排序，包括求N个元素中的最小的k个元素等。。。
堆是一种树形结构，它是一棵完全二叉树，其中堆又分为最小堆和最大堆。
最小堆：每个节点的键值都小于它的子树中的所有节点，所以最小堆的根节点的键值是整个堆中最小的。
最大堆：每个节点的键值都大于它的子树中的所有节点，所以最大堆的根节点的键值是整个堆中最大的。
于是，我们利用最大（小）堆的性质，可以在O(1)时间内得到n个元素中最小的值。
现在，我以最小堆为例，介绍一下它的实现方式：
用C++的类对heap进行封装：
MinHeap.h文件： class MinHeap{
private:
int count; //当前堆中的元素个数
int val ;
//用一维数组存储堆，其中节点 i 的左孩子是 2*i ,右孩子是 2*i + 1 ,根节点的键值是 val
void down(int position); //最小堆的调整函数
//void up(int position) 最大堆的调整函数
public:
MinHeap(); //构造函数
void Insert(int data ); //将data插入堆中
intTop_Remove() ; //返回堆顶元素，并把堆顶元素删去，重新调整堆
boolis_empty(); //返回堆是否为空，空则为 true，非空则为 false
int size(); //返回当前堆的大小——堆中元素的个数
};MinHeap.cpp 文件: //这里的代码风格借鉴了 Nisy老师上次共享的 DebuggerVC代码中的风格,好的代码风格就应该模仿。
///////////////////////////////////////////////////////////
// 函数名：MinHeap()
// 描述：构造函数,生成一个空堆
// 参数：None
// 前提：None
// 用法：MinHeap对象名
///////////////////////////////////////////////////////////
MinHeap :: MinHeap(){
count = 0;
}
///////////////////////////////////////////////////////////
// 函数名：is_empty()
// 描述：判断堆是否为空
// 参数：None
// 前提：None
// 用法：对象名.is_empty()
///////////////////////////////////////////////////////////
boolMinHeap :: is_empty(){
return (count == 0);
}
///////////////////////////////////////////////////////////
// 函数名：size()
// 描述：返回堆的大小
// 参数：None
// 前提：None
// 用法：对象名.size()
///////////////////////////////////////////////////////////
intMinHeap :: size(){
return count;
}
///////////////////////////////////////////////////////////
// 函数名：Insert()
// 描述：往堆中插入一个元素，并重新调整堆结构
// 参数：Data 表示插入元素的键值
// 前提：None
// 用法：对象名.Insert( xx )
///////////////////////////////////////////////////////////
void MinHeap :: Insert( int data)
{
val [++ count ] = data; //先将元素放入堆尾
intp = count ; //调整用指针
while(p > 1) { //在到达根节点之前
if( val[ p>>1 ] > val ){ //如果p的父节点键值＞p,进行交换
int tmp = val ;
val = val [ p>>1 ] ;
val = tmp;
p >> = 1; //指针向上移
}
else break; //如果没有破坏堆结构直接跳出。
}
}
///////////////////////////////////////////////////////////
// 函数名：down(int position)
// 描述：将当前破坏了的堆 通过下降调整为堆
// 参数：position 表示需要调整的位置
// 前提：None
// 用法：None
///////////////////////////////////////////////////////////
void MinHeap :: down(int position)
{
while( (position << 1) <= size ) //如果位置还没下降到叶子节点
{
int tmp = position << 1;
if( ( position << 1 ) + 1 <= size && val[ (position<<1)+1] < val )
//如果当前节点的右孩子小于当前节点的左孩子
tmp = ( possition<<1 )+ 1;
if( val < val ) {
//如果当前节点的右孩子 小于当前节点
int temp = val ;
val = val;
val = temp;
position = tmp;
}
else break;
}
}
///////////////////////////////////////////////////////////
// 函数名：Top_Remove()
// 描述：返回堆顶元素，并删除之，再重新调整堆结构
// 参数：None
// 前提：None
// 用法：对象名.Top_Remove()
///////////////////////////////////////////////////////////
int MinHeap :: Top_Remove(){
int temp = val ; //保存堆顶元素
val = val [ count];
val = temp;
count --;
down(1);调整整个堆
return val;
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ 以上给出了一个最小堆的具体实现方式，下面给出堆的实际应用
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
一、堆排序：
因为我们可以在O(1)时间复杂度内求出n个元素中的最值，于是我们就可以用它来排序。
思想是，将待排序元素 a 一一插入到这个堆中，那么，堆顶元素永远是最小的，于是，我们把堆顶元素放到最后，然后用新插入的元素来代替，接着重新调整堆，这样逐步迭代后，我们就可以得到一个 从大到小的有序序列。
时间复杂度： T(n) = N*O(logN) 插入时间= O(NlogN)
与快速排序算法的时间复杂度都很高，所以堆排序也是一种很好的稳定排序方式，它不太会像快排那样退化成O(n^2)
二、求出海量数据中的最小的n个元素——这里要用到最大堆，和最小堆的实现方式正好相反。
如果有海量的数据,求前n个元素并不简单，如果要先排序的话，时间复杂度非常高，这里就可以用到堆的思想。
对海量数据进行一次线性的扫描，然后把每个元素插入最大堆中，如果下一个元素小于堆顶元素，那么把堆顶元素删去，用下一个元素来代替，然后重新调整堆，再继续插入。
这样，最后堆中的n个元素就是最小的n个元素。
+++++++++++++++++++++++++++后记++++++++++++++++++++++++++
堆还有更多的用途，我这里只起到一个抛砖引玉的作用。
转载时请注明出处。
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 我上面说的堆 别和程序中的堆栈搞起来。。。一个是数据结构ADT，一个是系统的内存空间 飘云真是太好了 人才！不去分析XX，真是浪费了，你懂的~~ 回复 4# 飘云
谢谢老大赞赏…… 最近比较忙, 抽空看了几个破解视频, 觉得破解也是很有意思的。
页:
[1]