欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序

程序员文章站 2022-05-23 11:29:28
...

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) 调整各个节点位置,以满足最大堆的有序特性。
这个调整的基本思路是,从最后一个有子节点的元素开始,递归调整。即将左右子树调整成堆,再加入父节点再次调整。