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

发布日期:2019-02-17

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

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

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

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

 

一、关于堆

1、堆的定义:

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

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

(图示1)

 

2、堆的算法:

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

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

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

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

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

 

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

1 private void swim(int k) {// 二叉堆2 while (k > 1 && less(k / 2 k)) {3 exch(k / 2 k)4 k = k / 25 }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 = j12 }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 = temp7 L = n8 }

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

 

④、多叉堆(了解即可)

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

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 = k12 while (j <= N && j <= d * k + 1) {13 if (less(flag j)) {14 flag = j15 }16 j++17 }18 if (flag == k) {// flag没有改变19 break20 }21 exch(k flag)22 k = flag23 }24 }

 

二、堆排序(非降序):

(示意图2)

 

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

 

1 public void sort(Comparable[] a) {//堆排序 2 int n=N 3 for(int k=n/2k>=1k--) { 4 sink(kn) 5 } 6 while(n>1) { 7 exch(1n--) 8 sink(1n) 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 break104 }105 exch(k flag)106 k = flag107 }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 = temp116 L = n117 }118 119 private void exch(int i int j) {120 Key temp = pq[i]121 pq[i] = pq[j]122 pq[j] = temp123 }124 125 private boolean less(int i int j) {126 return pq[i].compareTo(pq[j]) < 0127 }128 129 public void sort(Comparable[] a) {//堆排序130 int n=N131 for(int k=n/2k>=1k--) {132 sink(kn)133 }134 while(n>1) {135 exch(1n--)136 sink(1n)137 }138 }139 140 private void sink(int k int n) {//二叉树 从k到n排序141 while (2 * k <= n) {142 int j = 2 * k143 if (j < n && less(j j + 1)) {144 j++145 }146 if (!less(k j)) {147 break148 }149 exch(k j)150 k = j151 }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=1i<=Ni++) {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)