堆排序
要实现堆排序首先要理解堆相关的一些重要概念。 (1)什么是堆,堆于优先队列的关系? 堆实际上是优先队列数据结构的实现,也可以说,堆是具有优先队列性质的容器实现。 优先队列是允许下面两个操作的数据结构:InsertDeleteMin 即 DeleteMin 尤其要强调的是DeleteMin的操作,这步操作目的是找
·
要实现堆排序首先要理解堆相关的一些重要概念。
(1)什么是堆,堆于优先队列的关系?
堆实际上是优先队列数据结构的实现,也可以说,堆是具有优先队列性质的容器实现。
优先队列是允许下面两个操作的数据结构:
- Insert
- DeleteMin
即 DeleteMin <----[优先队列] <----Insert
尤其要强调的是DeleteMin的操作,这步操作目的是找到,返回,或删除最小项。切记!不仅仅是简单的出队,是做了一系列换位后将最小元素置换出来。
提供了类似这样的deleteMin操作和Insert操作的即是优先队列的实现。
比如最容易想到的两种实现方式为:
[1] 以一个链表来实现,这样Insert操作很容易为O(1), deleteMin操作则需要遍历链表实现为O(n)
[2] 让一个链表始终保持排序状态,这样Insert操作变得复杂需要遍历链表才能确定插入位置,为O(n);deleteMin操作变为O(1)
堆也恰恰提供了这样的操作实现。并综合降低了Insert,deleteMin操作的复杂度。
我们常指的堆实际上是二叉堆,还有很多其他堆,如左式堆,斜堆,等等这里不介绍。!!
binary heap, 是一棵完全二叉树(不一定是满二叉树)每个结点的父节点都小于等于该节点,根节点除外。
完全二叉树有个非常非常重要的性质:可以用数组表示,而不需要用链表。 一定要理解此性质!!!
也就是说堆可以用数组实现。这样最大的好处是,可以在常数时间找到min,Insert操作为O(logn),deleteMin操作平均为O(logn)
对于堆排序的实现,为了思路清晰,方便,使用大顶堆。上面介绍的都是以小顶堆为基础的基本概念,将deleteMin改为deleteMax即可。
排序的简单思路是,因为每次都能得到最大值(根结点),所以每做一次deleteMax操作即可去除一个最大值。这样做n次变得到排序结果。
于是容易得到基本代码:
void HeapSort(int p[], int size)
{
BuildMaxHeap(p, size);
for(int i=size-1; i>0; i--)
{
DeleteMax(p, i);
}
}
问题转化为如何实现BuildMaxHeap, DeleteMax操作。并有良好的时间,空间复杂度。
设待排序列为数组p[n] 如果将p建成堆后,很明显p[0]为根结点,即最大值。
考虑每次DeleteMax操作后,堆的大小变为n-1,可将p[0]与最后一个元素交换,于是DeleteMax操作的效果可视为:
n个元素的堆序列 -> n-1个元素的堆序列|Max 如此循环下去便能完成排序。
这里的BuildMaxHeap, DeleteMax均会用到下滤算法:如果某个元素影响堆序性质(父节点>=孩子)则将较大的孩子结点与其对换,如此往复下去,直至该元素到达正确位置。
BuildMaxHeap,建堆的实现方式:由于所有树叶无需进行下滤(没有孩子), 所以只对0 - size/2的结点进行下滤即可。
DeleteMax 操作需要将最大值即p[0]与堆数组的最后一个元素(如p[n])互换,然后对p[0]进行下滤操作即可得到一个 n-1个元素堆序列|max
代码实现:
#include <iostream>
using namespace std;
//template <typename Comparable>
void BuildMaxHeap( int p [], int size);
void DeleteMax( int p [], int size);
void PercolateDown( int array [], int hole , int size);
void HeapSort( int p [], int size)
{
BuildMaxHeap(p , size);
for ( int i = size; i >= 1; i --)
{
DeleteMax(p , i);
}
}
void BuildMaxHeap( int p [], int size)
{
//由于所有树叶无需进行下滤(没有孩子), 所以只对0 - size/2的结点进行下滤即可。
for ( int i = size / 2 - 1; i >= 0; i --)
PercolateDown(p , i , size);
}
void DeleteMax( int p [], int size)
{
int tmp;
tmp = p [ 0 ];
p [ 0 ] = p [ size - 1 ];
p [ size - 1 ] = tmp;
PercolateDown(p , 0 , -- size);
}
void PercolateDown( int array [], int hole , int size)
{
int tmp = array [ hole ];
int child = 0;
for (; ( hole * 2 + 1) <=( size - 1); hole = child)
{
child = hole * 2 + 1;
if ( child < size - 1 && ( array [ child + 1 ] > array [ child ]))
child ++;
if ( array [ child ] > tmp)
array [ hole ] = array [ child ];
else
break;
}
array [ hole ] = tmp;
}
void PrintArray( int data [], int size)
{
for ( int i = 0; i < size; ++ i)
{
cout << data [ i ] << " ";
}
cout << endl;
}
int main( int argc , const char ** argv)
{
int data [] = { 20 , 34 , 4 , 53 , 43 , 42 , 6 , 67 , 193 };
int size = sizeof( data) / sizeof( data [ 0 ]);
HeapSort( data , size);
PrintArray( data , size);
return 0;
}
using namespace std;
//template <typename Comparable>
void BuildMaxHeap( int p [], int size);
void DeleteMax( int p [], int size);
void PercolateDown( int array [], int hole , int size);
void HeapSort( int p [], int size)
{
BuildMaxHeap(p , size);
for ( int i = size; i >= 1; i --)
{
DeleteMax(p , i);
}
}
void BuildMaxHeap( int p [], int size)
{
//由于所有树叶无需进行下滤(没有孩子), 所以只对0 - size/2的结点进行下滤即可。
for ( int i = size / 2 - 1; i >= 0; i --)
PercolateDown(p , i , size);
}
void DeleteMax( int p [], int size)
{
int tmp;
tmp = p [ 0 ];
p [ 0 ] = p [ size - 1 ];
p [ size - 1 ] = tmp;
PercolateDown(p , 0 , -- size);
}
void PercolateDown( int array [], int hole , int size)
{
int tmp = array [ hole ];
int child = 0;
for (; ( hole * 2 + 1) <=( size - 1); hole = child)
{
child = hole * 2 + 1;
if ( child < size - 1 && ( array [ child + 1 ] > array [ child ]))
child ++;
if ( array [ child ] > tmp)
array [ hole ] = array [ child ];
else
break;
}
array [ hole ] = tmp;
}
void PrintArray( int data [], int size)
{
for ( int i = 0; i < size; ++ i)
{
cout << data [ i ] << " ";
}
cout << endl;
}
int main( int argc , const char ** argv)
{
int data [] = { 20 , 34 , 4 , 53 , 43 , 42 , 6 , 67 , 193 };
int size = sizeof( data) / sizeof( data [ 0 ]);
HeapSort( data , size);
PrintArray( data , size);
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)