堆排序
1. 堆排序Heap_Sort
算法1.1
void Heap_Sort( ElementType A[], int N )
{
BuildHeap( A ); /*创建最小堆, 时间复杂度O(N)*/
/*TmpA 是存放排序结果的临时数组*/
/*DeleteMin 从最小堆里找到最小元素弹出*/
for( i=0; i<N; i++ )
TmpA[i] = DeleteMin(A); /*O(logN)*/
/*把数据还原到数组A*/
for( i=0; i<N; i++)
A[i] = TmpA[i];
}
T(N) = O(N*logN)
需要额外O(N)空间, 并且复制元素需要时间
算法1.2 实际堆排序
void Heap_Sort( ElementType A[], int N )
{
for( i=N/2; i>=0; i-- ) /*BuildHeap*/
PerDown(A, i, N);
for( i=N-1; i>0; i-- )
{
Swap( &A[0], &A[i] ); /*DeleteMax*/
PerDown(A, 0, i);
}
}
定理1.1:堆排序处理N个不同元素的随机排列的平均比较次数是
2N logN - O(Nlog logN)
虽然堆排序给出最佳平均时间复杂度,但实际效果不如用Sedgewick增量的希尔排序。
2. 堆的实现
堆的存储, 使用完全二叉树,用数组存储数据。
最大堆:根节点比左右子节点大
最小堆:根节点比左右节点小
2.1 最大堆
数据对象集:完全二叉树,每个节点的元素不小于其子节点的元素值
主要的操作有:
MaxHeap Create(int MaxSize); // 创建堆
Boolean IsFull(MaxHeap H); // 堆是否已满
Insert(MaxHeap H, ElementType item); // 将元素item插入最大堆H
Boolean IsEmpty(MaxHeap H); // 判断堆是否空的
ElementType DeleteMax(MaxHeap H);//返回H中最大元素(删除最大元素)
2.1.1 堆的结构体
typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
ElementType *Elements; /*存储堆元素的数组*/
int Size; /*堆的当前元素个数*/
int Capacity; /*堆的最大容量*/
};
2.1.2 创建堆
MaxHeap Create( int MaxSize )
{
MaxHeap H = malloc( sizeof( struct HeapStruct ) );
H->Elements = malloc( MaxSize+1 ) * sizeof( ElementType );
H->Size = 0;
/*定义"哨兵"为大于堆中所有可能元素的值,便于以后更快操作*/
H->Elements[0] = MaxData;
return H;
}
2.1.3 堆是否已满
Boolean IsFull(MaxHeap H)
{
return (H->size >= H->Capacity);
}
2.1.4 堆元素的插入
将新增节点插入到从其父节点到根节点的有序序列中 T = O(logN)
void Insert( MaxHeap H, ElementType item )
{ /*将元素item插入到最大堆H,其中H->Elements[0]已经定义为哨兵*/
int i;
if ( IsFull(H) ){ Error("堆已满"); return; }
i = ++H->Size; /*i指向插入后堆中的最后一个元素的位置*/
for (; H->Elements[i/2] < item; i/=2)
H->Elements[i] = H->Elements[i/2]; /*向下过滤节点*/
H->Elements[i] = item; /*将item插入*/
}
2.1.5 最大堆的删除
取出根节点(最大值)元素, 同时删除堆的一个节点。
ElementType DeleteMax(MaxHeap H)
{
int Parent, Child;
ElementType MaxItem, temp;
if ( IsEmpty(H) ) { Error("堆为空"); return ERROR;}
MaxItem = H->Elements[1]; /*取出根节点最大值*/
/*用最大堆中最后一个元素从根节点开始向上过滤下层节点*/
temp = H->Elements[H->Size--];
for( Parent=1; Parent*2 < H->Size; Parent=Child)
{
Child = Parent * 2;
if ( (Child != H->Size) &&
(H->Elements[Child] < H->Elements[Child+1]) )
Child++; /*Child指向的左右子节点的较大者*/
if ( temp >= H->Elements[Child] )
break;
else /*移动temp元素到下一层*/
H->Elements[Parent] = H->Elements[Child];
}
H->Elements[Parent] = temp;
return MaxItem;
}
2.1.6 堆是否空
Boolean IsEmpty(MaxHeap H)
{
return (H->size == 0);
}
2.1.7 最大堆的建立
建立最大堆: 将已经存储的N个元素按最大堆的要求存放在一个一维数组中。
方法1: 通过插入操作,将N个元素一个一个相继插入到一个初始为空的堆中去, 其时间代价最大为O(NlogN)
方法2: 在线性时间复杂度下建立最大堆
(1) 将N个元素按输入顺序存入,先满足完全二叉树的结构特性
(2) 调整各个节点位置,以满足最大堆的有序特性。
这个调整的基本思路是,从最后一个有子节点的元素开始,递归调整。即将左右子树调整成堆,再加入父节点再次调整。
上一篇: 用python写的一个wordpress的采集程序
下一篇: 从头开始的Java学习Day03(上)