[关闭]
@quinn 2015-04-08T01:53:55.000000Z 字数 3205 阅读 2495

优先队列和堆排序

排序算法 数据结构


1 优先队列

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (largest-in,first-out)的行为特征。

优先队列支持两种基本操作:向优先队列中插入一个新的数据项,删除(最大)优先队列中关键字最大的数据项。 优先队列具有很好的灵活性,能支持的操作:
- 根据N个数据项构造一个优先队列
- 插入一个数据项
- 删除最大值的数据项
- 改变任意给定的数据项的优先级
- 删除任意给定的数据项
- 合并两个优先队列为一个优先队列

排序:先插入所有记录,然后逐个删除最大元素得到逆序的记录。


[注] 研究各种数据结构,我们都将铭记两个基本的权衡策略: 链表内存分配和顺序内存分配(数组)。
不同的实现对于要执行的各种操作具有不同的性能特征,不同的应用问题需要高效的不同操作集的性能。如:有序表删除快插入慢,无序表删除慢插入快。

2 堆

堆的数据结构,能够支持优先队列的基本操作。在堆中,父节点中的关键字都大于或等于其子节点中的关键字。
如果一棵树中每个节点的关键字都大于或等于所有子节点的关键字(如果存在),称树是堆有序的。
堆是一个节点的集合,表示为数组,其中关键字按堆有序的完全二叉树的形式排列。直观想,我们应该用链表表示堆有序的树,但是完全二叉树给了我们使用压缩数组表示的机会。
这里写图片描述
在位置i处的父节点,两个子节点的位置分别是 2i 和 2i+1.

2.1 基于堆的算法

如果我们对基于堆的优先队列做一点简单修改,可以侵犯堆的条件,然后通过遍历堆,在需要的时候修改堆使其满足堆的条件,我们把这个过程称为堆化或修正堆。
有两种情况需要修正堆:
(1)某个节点的优先级增加或新节点被插入到堆底,需要向上遍历堆修复
(2)某个节点的优先级降低或删除了最大项,需要向下遍历堆修复

初始化

  1. //优先队列数据结构
  2. struct PQ
  3. {
  4. Item data[maxN];
  5. int N;
  6. };
  7. //初始化
  8. PQ* PQInit()
  9. {
  10. PQ* pq = (PQ*)malloc(sizeof(*pq));
  11. pq->N = 0;
  12. return pq;
  13. }

自底向上堆化

  1. //Insert一项时,从数组尾部插入,向上修复
  2. void PQFixUp(PQ *pq)
  3. {
  4. int k = pq->N; // k节点的父节点是 k/2
  5. while(k > 1 && less(pq->data[k/2], pq->data[k]))//共比较 lg N 次
  6. {
  7. exch(pq->data[k/2], pq->data[k]);
  8. k = k/2;
  9. }
  10. }

自顶向下堆化

如果节点关键字比它的一个或两个子节点的关键字小,那么交换该节点与较大的子节点,这种交换会影响子节点不满足堆性质,所以用同样的方法修正它。

  1. //删除最大(顶部)节点,从上向下 fix
  2. void PQFixDown(PQ *pq)
  3. {
  4. int k = 1;
  5. int N = pq->N;
  6. while(2*k <= N) //共比较 2*lg N 次(找更大的子节点lgN, 判断是否交换lgN)
  7. {
  8. int j = 2*k;
  9. if(j < N && less(pq->data[j], pq->data[j+1]))//找较大子节点
  10. j++;
  11. if(!less(pq->data[k], pq->data[j])) //父节点不小于最大的子节点时,fix完成
  12. break;
  13. exch(pq->data[k], pq->data[j]);
  14. k = j;
  15. }
  16. }

插入、删除一项

  1. //Insert an element,插入到数组尾部,然后向上fix
  2. void PQInsert(PQ *pq, Item v)
  3. {
  4. pq->data[++(pq->N)] = v;
  5. PQFixUp(pq);
  6. }
  7. //delete max-第一个节点;向下fix
  8. Item PQDelMax(PQ *pq)
  9. {
  10. if(PQIsEmpty(pq))
  11. {
  12. printf("Error: pq is empty. Can't delete Max\n");
  13. return -1;
  14. }
  15. exch(pq->data[1], pq->data[pq->N]);//交换最大的与最后一项
  16. (pq->N)--;//剔除最后一项(最大)
  17. PQFixDown(pq);
  18. return pq->data[pq->N + 1];
  19. }

删除时,如果无序表对用与选择排序,有序表对应于插入排序

2.2 堆排序

  1. void PQSort(Item a[], int l, int r)
  2. {
  3. PQ* pq = PQInit();
  4. int i;
  5. for(i = l; i <= r; i++)
  6. PQInsert(pq, a[i]);
  7. for(i = r; i >= l; i--)
  8. a[i] = PQDelMax(pq);
  9. }

优先队列全部代码

  1. /*======================================================
  2. Title:基于数组的优先队列实现:k父节点,2k、2k+1为子节点
  3. 数据项存储在数组的 1~N 项中。
  4. Functions: 插入一项,向上堆化保持有序;
  5. 删除并返回最大项,向下堆化保持有序
  6. Author: quinn
  7. Date: 2015/03/27
  8. =======================================================*/
  9. #include<stdlib.h>
  10. #include<stdio.h>
  11. #define maxN 100 //队列的最大容量
  12. typedef int Item;
  13. typedef struct PQ PQ;
  14. #define exch(A, B) {Item t; t = A; A = B; B = t;}
  15. #define less(A, B) (A < B)
  16. //优先队列数据结构
  17. struct PQ
  18. {
  19. Item data[maxN];
  20. int N;
  21. };
  22. //初始化
  23. PQ* PQInit()
  24. {
  25. PQ* pq = (PQ*)malloc(sizeof(*pq));
  26. pq->N = 0;
  27. return pq;
  28. }
  29. bool PQIsEmpty(PQ *pq)
  30. {
  31. return pq->N == 0;
  32. }
  33. //Insert一项时,从数组尾部插入,向上修复
  34. void PQFixUp(PQ *pq)
  35. {
  36. int k = pq->N;
  37. while(k > 1 && less(pq->data[k/2], pq->data[k]))//共比较 lg N 次
  38. {
  39. exch(pq->data[k/2], pq->data[k]);
  40. k = k/2;
  41. }
  42. }
  43. //删除最大(顶部)节点,从上向下 fix
  44. void PQFixDown(PQ *pq)
  45. {
  46. int k = 1;
  47. int N = pq->N;
  48. while(2*k <= N) //共比较 2*lg N 次(找更大的子节点lgN, 判断是否交换lgN)
  49. {
  50. int j = 2*k;
  51. if(j < N && less(pq->data[j], pq->data[j+1]))
  52. j++;
  53. if(!less(pq->data[k], pq->data[j])) //父节点不小于最大的子节点时,fix完成
  54. break;
  55. exch(pq->data[k], pq->data[j]);
  56. k = j;
  57. }
  58. }
  59. //Insert an element,插入到数组尾部,然后向上fix
  60. void PQInsert(PQ *pq, Item v)
  61. {
  62. pq->data[++(pq->N)] = v;
  63. PQFixUp(pq);
  64. }
  65. //delete max-第一个节点;向下fix
  66. Item PQDelMax(PQ *pq)
  67. {
  68. if(PQIsEmpty(pq))
  69. {
  70. printf("Error: pq is empty. Can't delete Max\n");
  71. return -1;
  72. }
  73. exch(pq->data[1], pq->data[pq->N]);
  74. (pq->N)--;
  75. PQFixDown(pq);
  76. return pq->data[pq->N + 1];
  77. }
  78. int main()
  79. {
  80. PQ* pq = PQInit();
  81. for(int i = 0; i < 10; i++)
  82. PQInsert(pq, i);
  83. for (int i = 0; i < 11; ++i)
  84. {
  85. printf("%d\n", PQDelMax(pq));
  86. }
  87. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注