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

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

程序员文章站 2024-02-15 09:31:58
...
堆的应用之优先级队列,用堆封装优先级队列
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;
}
数据结构:堆的应用之优先级队列,用堆封装优先级队列 及 实现堆排序
相关标签: 数据结构