数据结构:堆的应用之优先级队列,用堆封装优先级队列 及 实现堆排序
程序员文章站
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);
// 销毁优先级队列
![数据结构:堆的应用之优先级队列,用堆封装优先级队列 及 实现堆排序 数据结构:堆的应用之优先级队列,用堆封装优先级队列 及 实现堆排序](/default/index/img?u=aHR0cHM6Ly93d3cuZnJlZXNpb24uY29tL2ltYWdlcy8zMjgvYWRmYzYxOGZkNTljYmQ3ZGNiMzhjN2Q1YjRhYWFhZTAucG5n)
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;
}
上一篇: java验证码组件kaptcha使用方法
下一篇: java多线程和并发包入门示例