堆和优先队列的应用
<div id="cnblogs_post_body">什么是堆：堆的定义：n个元素的序列k={k0,k1,&hellip;&hellip;,kn-1},当且仅满足条件
(1)ki >= k2i+1 和 ki >= k2i+2 (2)ki <= k2i+1 和 ki <= k2i+2
(1)称为大根堆 (2)称为小根堆
可以把堆看成完全二叉树。
什么是优先队列：
优先队列是一种常见的抽象数据类型，它与"队列"不同，不遵循"先进先出"原则，而遵循"最小元素先出"原则。
优先队列的基本操作有三个：
(1) 向优先队列里插入一个元素
(2) 在优先队列找出最小元素
(3) 删除优先队列中最小元素
可以用堆来实现有限队列
优先队列的实现：
<div class="cnblogs_code">1 #include "stdio.h"2 #include "stdlib.h"3 4 typedef int DATATYPE;5 6 /********************优先队列存储结构********************************/7 struct priorityQueue 8 {9 int MAXNUM; //存储结构长度 10 int n; //实际元素个数 11 DATATYPE * element; 12 }; 13 typedef struct priorityQueue *PQ; 14 15 /********************创建优先队列***********************************/ 16 PQ createPQ(int maxnum) 17 { 18 PQ pq = NULL; 19 pq = (PQ) malloc(sizeof(struct priorityQueue)); 20 if(NULL != pq) 21 { 22 pq->element = malloc(sizeof(DATATYPE) * maxnum); 23 if(pq->element != NULL) 24 { 25 pq->MAXNUM = maxnum; 26 pq->n = 0; 27 } 28 } 29 return pq; 30 } 31 32 /****************************判断优先队列是否为空****************************/ 33 int isEmpty_heap(PQ pq) 34 { 35 return pq->n == 0; 36 } 37 38 /**************************往优先队列中插入元素*******************************/ 39 void add_heap(PQ pq, DATATYPE x) 40 { 41 int i = -1; //标志元素最后要插入位置的下标 42 if(pq->n >= pq->MAXNUM) //如果队列已满，无法插入 43 { 44 printf("PriorityQueue is full"); 45 return; 46 } 47 //寻找插入的位置,pq->n是未有元素的空位 48 for(i = pq->n; i > 0 && x < pq->element[(i-1)/2]; i = (i - 1)/2) 49 { 50 pq->element = pq->element[(i-1)/2]; 51 } 52 //插入元素 53 pq->element = x; 54 pq->n++; 55 } 56 57 /*************************在三个元素中，找出最小元素的下标********************/ 58 int findMinIndex(PQ pq,int index1, int index2, int index3) 59 { 60 int min = 0; 61 min = (pq->element < pq->element)?index1:index2; 62 min = (pq->element < pq->element)?min:index3; 63 return min; 64 } 65 66 /*************************删除优先队列最小元素************************************/ 67 void removeMin_heap(PQ pq) 68 { 69 int endIndex,leftchild,rightchild,index,minIndex; 70 if(isEmpty_heap(pq)) //如果为空队列，返回 71 return; 72 endIndex = --pq->n; //找到队列尾元素下标,并将首元素删除 73 74 index = 0; //空位的下标，开始时在根节点处 75 for(;index < endIndex;) 76 { 77 leftchild = index*2 + 1; 78 rightchild = index*2 + 2; 79 if(leftchild > endIndex || rightchild > endIndex) 80 { 81 pq->element = pq->element; 82 break; 83 } 84 85 minIndex = findMinIndex(pq,endIndex,leftchild,rightchild); 86 pq->element = pq->element; 87 if(minIndex == endIndex) 88 break; 89 else if(minIndex == leftchild) 90 index = leftchild; 91 else if(minIndex == rightchild) 92 index = rightchild; 93 } 94 } 95 96 97 98 /***********************显示优先队列中元素的排列****************************/ 99 void show(PQ pq)100 {101 int i = 0;102 103 for(i = 0; i < pq->n; i++)104 {105 printf("%d, ",pq->element);106 }107 108 }109 110 int main()111 {112 PQ pq = createPQ(6);113 add_heap(pq, 3);114 add_heap(pq, 2);115 add_heap(pq, 8);116 add_heap(pq, 4);117 add_heap(pq, 6);118 add_heap(pq, 10);119 120 show(pq);121 printf("\n");122 123 removeMin_heap(pq);124 show(pq);125 return 0;126 }
页:
[1]