什么是优先队列?
优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT来完成操作,优先队列ADT是一种数据结构,它支持插入和删除最小值操作(返回并删除最小元素)或删除最大值操作(返回并删除最大元素);
这些操作等价于队列的enQueue
和deQueue
操作,区别在于,对于优先队列,元素进入队列的顺序可能与其被操作的顺序不同,作业调度是优先队列的一个应用实例,它根据优先级的高低而不是先到先服务的方式来进行调度;
如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素),类似的,如果最大键值元素拥有最高的优先级,那么这种优先队列叫作降序优先队列(即总是先删除最大的元素);由于这两种类型时对称的,所以只需要关注其中一种,如升序优先队列;
堆的代码
#include <stdio.h>
#include <assert.h>
#include<iostream>
using namespace std;
#define _CRT_SECURE_N0_WARNINGS 1
struct Heap{
int array[100];
int size;
};
static void Swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
//初始化
void HeapInit(Heap *pH, int source[], int size)
{
for (int i = 0; i < size; i++)
{
pH->array[i] = source[i];
}
//更改堆的实际大小
pH->size = size;
}
//向下调整 大堆
//root 指的是下标 ------------->大根堆
void HeapAdjustDown(Heap* pH, int root)
{
int parent = root;
while (true)
{
// 先判断有没有孩子(叶子结点)
// 数组角度去想 -> 孩子的下标是否越界
// 只要判断左孩子的下标(因为是完全二叉树)
int left = parent * 2 + 1;
int right = parent * 2 + 2;
if (pH->size < left) //越界 左孩子不存在
return;
int MaxChild = left;
if ((pH->size >= right) && (pH->array[right]>pH->array[MaxChild]))
MaxChild = right;
if (pH->array[MaxChild] < pH->array[parent])
return;
//交换
swap(pH->array[MaxChild],pH->array[parent]);
parent = MaxChild;
}
}
//向上调整 大堆
void HeapAdjustUp(Heap* pH, int child)
{
int parent;
while (child > 0)
{
parent = (child - 1) / 2;
if (pH->array[parent] >= pH->array[child])
return;
Swap(pH->array + parent, pH->array + child);
child = parent;
}
}
void HeapMakeHeap(Heap* pH)
{
//最后一个非叶子结点 last=size-1;
//parent=(last-1)/2 = size/2-1;
//所有非叶子结点的下标为[0 ,size/2-1]
//从物理结构上来看 从后往前建堆 [最后一个非叶子结点size/2-1,0]
for (int i = (pH->size - 2) / 2; i >= 0; i--) {
HeapAdjustDown(pH, i);
}
}
void HeapPop(Heap* pH)
{
pH->array[0] = pH->array[pH->size - 1];
pH->size = pH->size - 1;
HeapAdjustDown(pH, 0);
}
int HeapTop(Heap* pH)
{
return pH->array[0];
}
void HeapPush(Heap* pH,int data)
{
assert(pH->size < 100);
pH->array[pH->size++] = data;
HeapAdjustUp(pH, pH->size-1);
}
void Test()
{
int array[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
int size = sizeof(array) / sizeof(int);
Heap heap;
HeapInit(&heap, array, size);
HeapMakeHeap(&heap);
HeapPop(&heap);
HeapPush(&heap, 100);
printf("%d
", HeapTop(&heap));
printf("Create dump
");
}
int main()
{
Test();
return 0;
}