数据结构：堆的应用之优先级队列，用堆封装优先级队列 及 实现堆排序

堆的应用之优先级队列，用堆封装优先级队列
typedef struct PriorityQueue
{
Heap _hp;
}PriorityQueue;

// 优先级队列初始化
void PriorityQueueInit(PriorityQueue* q, Compare com);

// 向队列中插入元素
void PriorityQueuePush(PriorityQueue* q, DataType data);

// 删除优先级最高的元素
void PriorityQueuePop(PriorityQueue* q);

// 获取队列中优先级最高的元素
int PriorityQueueSize(PriorityQueue* q);

// 检测优先级队列是否为空
int PriorityQueueEmpty(PriorityQueue* q);

// 获取堆顶的元素
DataType PriorityQueueTop(PriorityQueue* q);

// 销毁优先级队列

void PriorityQueueDestroy(PriorityQueue* q);

堆代码实现：

                                点击打开链接

用堆的思想实现堆排序，给出代码实现 :

堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

Priorityqueue.h

#pragma once
#include"Heap.h"

typedef struct Priorityueue
{
	Heap _hp;
}PriorityQueue;


// 优先级队列初始化 
void PriorityQueueInit(PriorityQueue* q, Compare com);

// 向队列中插入元素 
void PriorityQueuePush(PriorityQueue* q, DataType data);

// 删除优先级最高的元素 
void PriorityQueuePop(PriorityQueue* q);

// 获取队列中优先级最高的元素 
int PriorityQueueSize(PriorityQueue* q);

// 检测优先级队列是否为空 
int PriorityQueueEmpty(PriorityQueue* q);

// 获取堆顶的元素 
DataType PriorityQueueTop(PriorityQueue* q);

// 销毁优先级队列 
void PriorityQueueDestroy(PriorityQueue* q);

Priorityqueue.c

#include"Priorityqueue.h"

// 优先级队列初始化 
void PriorityQueueInit(PriorityQueue* q, Compare com)
{
	InitHeap(&q->_hp,com);
}

// 向队列中插入元素 
void PriorityQueuePush(PriorityQueue* q, DataType data)
{
	InsertHeap(&q->_hp,data);
}

// 删除优先级最高的元素 
void PriorityQueuePop(PriorityQueue* q)
{
	DeleteHeap(&q->_hp);
}

// 获取队列中优先级最高的元素 
int PriorityQueueSize(PriorityQueue* q)
{
	return SizeHeap(&q->_hp);
}

// 检测优先级队列是否为空 
int PriorityQueueEmpty(PriorityQueue* q)
{
	return EmptyHeap(&q->_hp);
}

// 获取堆顶的元素 
DataType PriorityQueueTop(PriorityQueue* q)
{
	return TopHeap(&q->_hp);
}

// 销毁优先级队列 
void PriorityQueueDestroy(PriorityQueue* q)
{
	DestroyHeap(&q->_hp);
}

//void test()//用堆封装优先级队列测试
//{
//	PriorityQueue q;
//	PriorityQueueInit(&q, Less);
//
//	PriorityQueuePush(&q, 1);
//	printf("%d ->", PriorityQueueTop(&q));
//	PriorityQueuePush(&q, 2);
//	PriorityQueuePop(&q);
//	printf("%d ->", PriorityQueueTop(&q));
//	PriorityQueuePush(&q, 3);
//	PriorityQueuePop(& q);
//	printf("%d ->", PriorityQueueTop(&q));
//	PriorityQueuePush(&q, 4);
//	PriorityQueuePop(&q);
//	printf("%d ->", PriorityQueueTop(&q));
//}
//int main()
//{
//	test();
//	system("pause");
//	return 0;
//}

void HeapAdjust(int*  array,int size, int parent)
{
	//升序——大堆
	int child = parent * 2 + 1;
	assert(array);
	while (child < size)//左孩子存在
	{
		if (child + 1 < size && array[child] < array[child + 1])//右孩子存在且大于左孩子
		{
			child += 1;
		}
		if (array[child] >  array[parent])
		{
			swap(&array[parent],&array[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			return;
	}
}
void HeapSore(int*  array, int size)
{
	//建堆
	int root = (size - 2) >> 1;//最后一个非叶子节点
	int end = size - 1;
	for (;root >= 0;--root)
		HeapAdjust(array,size, root);
	//排序
	while (end)
	{
		swap(&array[0],&array[end]);
		HeapAdjust(array,end, 0);
		end--;
	}
}

void TestHeapSore()
{
	int i = 0;
	int arr[] = { 53,17,78,9,45,65,87,23,31};
	int size = sizeof(arr) / sizeof(arr[0]);
	HeapSore(arr, size);
	for (; i < size;i++)
	{
		printf("%d->",arr[i]);
	}
	printf("\n");
}
int main()
{
	TestHeapSore();
	system("pause");
	return 0;
}