cat188
  咨询电话:13950049797

mrcat猫先生菠菜

排序算法之——优先队列经典实现(基于二叉堆)

许多应用都需要处理有序的元素,但有时,我们不要求所有元素都有序,或是一定要一次就将它们排序,许多情况下,我们会收集这些元素里的最大值或最小值。

这种情况下一个合适的数据结构应该支持两种操作:插入元素、删除最大元素。

优先队列与栈和队列类似,但它有自己的奇妙之处。

在本文中,会讲解基于二叉堆的一种优先队列的经典实现方法(代码没有任何难度,主要是理解思想)。

 

一、关于堆

1、堆的定义:

 数据结构二叉堆能很好地实现优先队列的操作。在二叉堆中,每个元素都要保证大于等于另外两个位置的元素,相应的,这些位置的元素又至少要大于等于数组中的另外两个元素。

将所有元素画成一颗二叉树,就能很容易看出这种结构。

(图示1)

 

2、堆的算法:

在堆有序的过程中我们会遇到两种情况:

某个节点的优先级上升,我们需要由下至上恢复堆的顺序。

当某个节点的优先级下降,我们需要由上至下恢复堆的顺序。

在排序算法中,我们只通过私有辅助函数来访问元素:

1 private void exch(int i, int j) {2 Key temp = pq[i];3 pq[i] = pq[j];4 pq[j] = temp;5 }6 7 private boolean less(int i, int j) {8 return pq[i].compareTo(pq[j]) < 0;9 }

 

①、由下至上的堆的有序化(上浮)

1 private void swim(int k) {// 二叉堆2 while (k > 1 && less(k / 2, k)) {3 exch(k / 2, k);4 k = k / 2;5 }6 }

k/2即为k节点的父节点,当k大于k/2时交换两者,并继续与其父节点比较,直到找到合适的位置。

 

②、由上至下的堆的有序化(下沉)

1 private void sink(int k) {// 二叉堆 2 while (2 * k <= N) { 3 int j = 2 * k; 4 if (j < N && less(j, j + 1)) { 5 j++; 6 } 7 if (!less(k, j)) { 8 break; 9 }10 exch(k, j);11 k = j;12 }13 }

对于二叉树,2*k即为k的左子节点,将左右子节点进行比较,再将父节点与较大的子节点比较,如果子节点大于父节点,就将他们交换,并继续向下比较,直到找到合适的位置。

 

③、调整数组大小

如果不知道元素的个数,任意在初始化时造成空间的浪费。我们需要创造一个函数,用来调整数组的大小。

在插入方法中,如果空间已满,就将数组大小扩展为原来的两倍。在删除方法中,如果元素的个数小于数组长度的1/4,就将数组的长度减小一半。

1 private void resize(int n) {2 Key[] temp = (Key[]) new Comparable[n + 1];3 for (int i = 1; i <= N; i++) {4 temp[i] = pq[i];5 }6 pq = temp;7 L = n;8 }

有了上面的方法,我们只需在插入和删除方法中加入判断语句即可。

 

④、多叉堆(了解即可)

 在掌握了二叉堆的原理之后,将其改进为多叉堆只需要做几个改动。下面直接放代码,有兴趣的朋友可以自己动手。

1 private void swim(int k, int d) {// d叉堆:(k+d-2)/d为d叉堆第k个节点的父节点 2 while (k > 1 && less((k + d - 2) / d, k)) { 3 exch((k + d - 2) / d, k); 4 k = (k + d - 2) / d; 5 } 6 } 7 8 private void sinkM(int k, int d) {// d叉堆 9 while (d * k - (d - 2) <= N) {// d叉堆k节点的第一个子节点10 int j = d * k - (d - 2);11 int flag = k;12 while (j <= N && j <= d * k + 1) {13 if (less(flag, j)) {14 flag = j;15 }16 j++;17 }18 if (flag == k) {// flag没有改变19 break;20 }21 exch(k, flag);22 k = flag;23 }24 }

 

二、堆排序(非降序):

(示意图2)

 

堆排序的sink()方法经过修改sink(a,b)中a是被排序的元素,b为排序的最大范围(修改之前排序的最大范围为元素总个数)。

 

1 public void sort(Comparable[] a) {//堆排序 2 int n=N; 3 for(int k=n/2;k>=1;k--) { 4 sink(k,n); 5 } 6 while(n>1) { 7 exch(1,n--); 8 sink(1,n); 9 }10 }

 

1、heap construction(堆的构造)

 可以看到在for循环中,我们只扫描了数组一半元素,因为我们跳过了大小为1的子堆,每次对一个节点排序时,以该节点为根节点的子堆就是有序的,所以我们最后会得到一个堆有序的二叉堆。

2、sortdown(下沉排序)

 下沉排序每次选出最大的元素放入数组空出的位置,这有点像选择排序,但所需的比较要小得多,因为堆提供了一种从未排序部分找到最大元素的有效方法。

 

 

三、java代码展示(所有代码)

1 public class MaxPQ<Key extends Comparable<Key>> { 2 private Key[] pq; 3 private static int N = 0;// 元素个数 4 private static int L;// 数组长度(不包括0) 5 6 public MaxPQ(int maxN) { 7 pq = (Key[]) new Comparable[maxN + 1]; 8 L = maxN; 9 } 10 11 public boolean isEmpty() { 12 return N == 0; 13 } 14 15 public int size() { 16 return N; 17 } 18 19 public void insert(Key v) {// 二叉堆 20 if (N == L) { 21 resize(2 * N + 1); 22 System.out.println("resize Double"); 23 } 24 pq[++N] = v; 25 swim(N); 26 } 27 28 public void insert(Key v, int d) {// d叉堆 29 if (N == L) { 30 resize(2 * N + 1); 31 System.out.println("resize Double"); 32 } 33 pq[++N] = v; 34 swim(N, d); 35 } 36 37 public Key delMax() { 38 Key max = pq[1]; 39 exch(1, N--); 40 pq[N + 1] = null; 41 sink(1); 42 if (N > 0 && N == L / 4) { 43 resize(L / 2); 44 System.out.println("resize 1/2"); 45 } 46 return max; 47 } 48 49 public Key delMax(int d) { 50 if (N == 0) { 51 System.out.println("none!"); 52 } 53 Key max = pq[1]; 54 exch(1, N--); 55 pq[N + 1] = null; 56 sinkM(1, d); 57 if (N > 0 && N == L / 4) { 58 resize(L / 2); 59 System.out.println("resize 1/2"); 60 } 61 return max; 62 } 63 64 private void swim(int k) {// 二叉堆 65 while (k > 1 && less(k / 2, k)) { 66 exch(k / 2, k); 67 k = k / 2; 68 } 69 } 70 71 private void swim(int k, int d) {// d叉堆:(k+d-2)/d为d叉堆第k个节点的父节点 72 while (k > 1 && less((k + d - 2) / d, k)) { 73 exch((k + d - 2) / d, k); 74 k = (k + d - 2) / d; 75 } 76 } 77 78 private void sink(int k) {// 二叉堆 79 while (2 * k <= N) { 80 int j = 2 * k; 81 if (j < N && less(j, j + 1)) { 82 j++; 83 } 84 if (!less(k, j)) { 85 break; 86 } 87 exch(k, j); 88 k = j; 89 } 90 } 91 92 private void sinkM(int k, int d) {// d叉堆 93 while (d * k - (d - 2) <= N) {// d叉堆k节点的第一个子节点 94 int j = d * k - (d - 2); 95 int flag = k; 96 while (j <= N && j <= d * k + 1) { 97 if (less(flag, j)) { 98 flag = j; 99 }100 j++;101 }102 if (flag == k) {// flag没有改变103 break;104 }105 exch(k, flag);106 k = flag;107 }108 }109 110 private void resize(int n) {111 Key[] temp = (Key[]) new Comparable[n + 1];112 for (int i = 1; i <= N; i++) {113 temp[i] = pq[i];114 }115 pq = temp;116 L = n;117 }118 119 private void exch(int i, int j) {120 Key temp = pq[i];121 pq[i] = pq[j];122 pq[j] = temp;123 }124 125 private boolean less(int i, int j) {126 return pq[i].compareTo(pq[j]) < 0;127 }128 129 public void sort(Comparable[] a) {//堆排序130 int n=N;131 for(int k=n/2;k>=1;k--) {132 sink(k,n);133 }134 while(n>1) {135 exch(1,n--);136 sink(1,n);137 }138 }139 140 private void sink(int k, int n) {//二叉树 从k到n排序141 while (2 * k <= n) {142 int j = 2 * k;143 if (j < n && less(j, j + 1)) {144 j++;145 }146 if (!less(k, j)) {147 break;148 }149 exch(k, j);150 k = j;151 }152 }153 154 public static void main(String[] args) {155 MaxPQ mpq = new MaxPQ<>(3);156 mpq.insert(1);157 mpq.insert(2);158 mpq.insert(3);159 mpq.insert(4);160 mpq.insert(5);161 mpq.insert(6);162 mpq.insert(7);163 mpq.insert(8);164 mpq.insert(9);165 mpq.insert(10);166 mpq.insert(11);167 mpq.sort(mpq.pq);168 for(int i=1;i<=N;i++) {169 System.out.println(mpq.pq[i]);170 }171 /*for (int i = 1; i <= 13; i++) {172 System.out.println(mpq.delMax());173 }*/174 }175 176 }

 

, 1, 0, 9);