堆排序

目录

一、基本原理

二、代码实现

1、二叉堆

2、堆排序

3、优先队列


 

一、基本原理

堆排序基于二叉堆(大顶堆、小顶堆)这一数据结构,二叉堆形状上就是完全二叉树。大顶堆就是任何一个节点都大于等于它的左孩子、右孩子;小顶堆则是任何一个节点都小于等于它的左孩子、右孩子。这两种结构的特点在于最大值、最小值放在堆顶的位置,另外父节点大于或小于其左右孩子节点。堆排序就是将数组转换为最大堆的形式,然后不断删除堆顶元素将其放在最后面的位置,同时重新维护成最大堆,当堆中元素为空时排序也就完成。

堆排序有些类似于选择排序,它每一轮将最大值上浮到数组最左端,然后将其交换到数组未排序的右端。与快速排序相比,两者平均时间复杂度均为O(nlogn),都是不稳定排序。不过,快排的最差时间复杂度为O(n^2)而堆排序最差也稳定在O(nlogn),在空间方面,快排的递归和非递归都是O(n)而堆排序是O(1)。与归并排序相比,两者时间复杂度的上界均为O(nlogn),两者的区别在于,归并排序的常数小于堆排序,堆排序使用的空间小于归并排序(O(n))。堆排序很少使用,一般仅在可用空间较少(无法使用归并排序)的实时(或快排无法适应时间限制)嵌入式系统中使用。

在O(nlogn)级别的排序算法中,堆排序不像快速排序、归并排序在实践中经常使用到,但是堆这种结构在很多地方经常用到。堆有如下应用场景:1)优先队列:使用二叉堆而不是二叉树实现优先队列(图算法如普里姆算法、地杰斯特拉算法会用到优先队列),因为二叉堆可以提供O(logn)时间复杂度的insert(),delete(),extractMax(),decreaseKey()等操作。二叉堆的变种二项堆和斐波那契堆(Binomoial Heap and Fibonacci Heap)可以提供O(logn)级别的union操作,这在二叉堆中需要O(n)的时间。2)统计:堆结构可以高效求解数组中第k小/大元素等问题。

 

二、代码实现

1、二叉堆

二叉堆是实现优先级队列、堆排序的基础。二叉堆的主要操作有二叉堆的构建、删除、插入,基本操作有最后一个元素的上浮调整和任一元素的下沉调整,其中,二叉堆的构建本质上就是所有非叶子节点的下沉调整;删除操作则是用最后一个元素替换堆顶元素,然后对堆顶元素进行下沉调整;插入操作则是在堆后面插入一个元素,然后对堆中最后一个元素进行上浮调整。此外,二叉堆也可以实现减小或增大节点的值、合并两个堆等操作。合并两个堆的最优方法是将两个二叉堆(元素个数分别为n、k)首尾相连放在一个数组中,然后构建新的二叉堆,时间复杂度为O(logn*logk)。如果经常需要合并两个堆的操作,那么使用二项式堆更好,其时间复杂度为O(logn)。

这里的二叉堆采用数组作为物理存储结构,因为当父节点的下标为 i 时,其左孩子的下标为2*i + 1,右孩子的下标为2*i + 2(如果存在的话,i = 0, 1, 2, ...),父节点为(i - 1) / 2,可以随机访问。另外,从左到右遍历数组相当于对二叉堆进行层序遍历。

1public class MaxHeap { 2 private int[] data; 3 private int size; //堆的实际大小 4 private int maxSize; //堆的最大大小 5 6 public MaxHeap(int capacity) { 7 data = new int[capacity + 1]; 8 maxSize = capacity; 9 size = 0; 10 data[0] = Integer.MAX_VALUE; 11 } 12 13 //返回节点i的父节点的下标 14 private int parent(int i) { 15 return i / 2; 16 } 17 //返回节点i的左孩子节点的下标 18 private int leftChild(int i) { 19 return 2 * i; 20 } 21 //返回节点i的右孩子节点的下标 22 private int rightChild(int i) { 23 return 2 * i + 1; 24 } 25 26 //判断给定节点是否是叶子节点 27 private boolean isLeaf(int i) { 28 if (i > (size / 2) && i <= size) { 29 return true; 30 } 31 return false; 32 } 33 //交换两个位置的元素 34 private void swap(int i, int j) { 35 int temp = data[i]; 36 data[i] = data[j]; 37 data[j] = temp; 38 } 39 //打印堆中所有元素 40 public void print() { 41 int num = 1; 42 int start = 1; 43 int step = 1; 44 for (int i=1; i<=size; i++) { 45 System.out.print(data[i] +" "); 46 if (i - start + 1 == step) { 47 step = step * 2; 48 start = i + 1; 49 System.out.println(); 50 } 51 } 52 } 53 54 //对堆中最后一个元素进行上浮调整 55 public void upAdjust() { 56 int i = size; 57 while (i/2 > 0 && data[i] > data[i/2]) { 58 swap(i, i/2); 59 i = i / 2; 60 } 61 } 62 //对堆中pos处的元素进行下沉调整(堆化子树) 63 public void downAdjust(int pos) { 64 int temp = data[pos]; 65 66 int parentIndex = pos; 67 int childIndex = leftChild(parentIndex); 68 while (childIndex < size) { 69 //拿到cur节点较大的孩子节点 70 if (childIndex+1<size && data[childIndex+1]>data[childIndex]){ 71 childIndex = childIndex + 1; 72 } 73 //如果父节点均大于等于两个孩子节点,直接跳出 74 if (temp >= data[childIndex]) { 75 break; 76 } 77 //交换父子节点(直接赋值即可,无需交换) 78 data[parentIndex] = data[childIndex]; 79 parentIndex = childIndex; 80 childIndex = leftChild(childIndex); 81 } 82 data[parentIndex] = temp; 83 } 84 //下沉调整的另一种写法 85 private void heapify(int i) { 86 while (true) { 87 int maxPos = i; 88 if (i+2 <= size && data[i]<data[i*2]) { 89 maxPos = i*2; 90 } 91 if (i*2+1 <= size && data[maxPos]<data[i*2+1]) { 92 maxPos = i*2 + 1; 93 } 94 95 if (maxPos == i) { 96 break; 97 } 98 swap(i, maxPos); 99 i = maxPos; 100 } 101 } 102 //下沉调整的递归写法 103 private void maxHeapify(int pos) { 104 if (isLeaf(pos)) { 105 return; 106 } 107 108 if ((leftChild(pos)<=size && data[pos]<data[leftChild(pos)]) || 109 (rightChild(pos)<=size && data[pos]<data[rightChild(pos)])) { 110 if (data[leftChild(pos)] > data[rightChild(pos)]) { 111 swap(pos, leftChild(pos)); 112 maxHeapify(leftChild(pos)); 113 } else { 114 swap(pos, rightChild(pos)); 115 maxHeapify(rightChild(pos)); 116 } 117 } 118 } 119 120 //插入元素 121 public void insert(int e) { 122 if (size >= maxSize) { 123 return; //堆满了 124 } 125 126 ++size; 127 data[size] = e; 128 upAdjust(); 129 } 130 //删除最大元素 131 public int extractMax() throws Exception { 132 if (size == 0) { 133 throw new Exception("Heap is empty"); 134 } 135 136 int temp = data[1]; 137 138 data[1] = data[size--]; 139 maxHeapify(1); 140 141 return temp; 142 } 143 //查询最大元素 144 public int getMax() { 145 if (size == 0) { 146 return Integer.MIN_VALUE; 147 } 148 return data[1]; 149 } 150 151} 152

利用优先队列创建大顶堆,由于PriorityQueue默认是小顶堆,这里需要使用Collections.reverseOrder()方法。

1public class MaxHeap { 2 3 public static void main(String[] args) { 4 5 //使用优先队列得到大顶堆 6 PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); 7 heap.add(10); 8 heap.add(30); 9 heap.add(20); 10 heap.add(400); 11 heap.add(400); 12 13 //删除堆顶元素、查看堆顶元素 14 System.out.println(heap.poll() +" "+ heap.peek()); 15 //遍历堆中元素 16 Iterator<Integer> itr = heap.iterator(); 17 while (itr.hasNext()) { 18 System.out.print(itr.next()+" "); 19 } 20 System.out.println(); 21 //获得元素数组 22 Object[] arr = heap.toArray(); 23 for (int i=0; i<arr.length; i++) { 24 //System.out.print(arr[i].toString()+" "); 25 System.out.print(arr[i]+" "); 26 } 27 System.out.println(); 28 29 } 30 31} 32

运行结果为:

2、堆排序

堆排序的基础是二叉堆的节点下沉调整操作。要实现堆排序,第一步需要将无序数组构建为大顶堆,第二步循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶。具体流程如下:

1)由输入数据构建一个大顶堆,此时最大元素被放在堆顶;

2)将堆顶元素与最后一个元素交换,并将堆的大小减1,确定堆中最大元素的最终位置(类似于选择排序);

3)对交换后的堆顶元素进行下沉调整,重复以上步骤直到堆中元素只有一个或为空。

1public class Sort { 2 3 //堆排序 4 public static void heapSort(int[] arr) { 5 //buildHeap(arr, arr.length-1); 6 buildHeap(arr); 7 int k = arr.length - 1; 8 //while (k >= 0) { 9 while (k > 0) { 10 swap(arr, 0, k); 11 --k; 12 //heapify(arr, k, 0); 13 downAdjust(arr, k, 0); 14 } 15 } 16 17 //堆的构建 18 //将整个数组调整为大顶堆(本质上就是让所有非叶子节点下沉) 19 private static void buildHeap(int[] arr) { 20 if (arr == null) { 21 return; 22 } 23 //从最后一个非叶子节点开始,依次进行下沉调整 24 for (int i=(arr.length-2)/2; i>=0; i--) { 25 //heapify(arr, arr.length-1, i); 26 downAdjust(arr,arr.length-1, i); 27 } 28 System.out.println(Arrays.toString(arr)); 29 } 30 //将数组arr[0 ... n]构建为大顶堆 31 private static void buildHeap(int[] arr, int n) { 32 if (arr == null) { 33 return; 34 } 35 for (int i=n/2; i>=0; i--) { 36 //heapify(arr, n, i); 37 downAdjust(arr, n, i); 38 } 39 System.out.println(Arrays.toString(arr)); 40 } 41 42 //对数组最后一个元素进行上浮调整,堆的范围为[0 ... arr.length-1] 43 private static void upAdjust(int[] arr) { 44 int childIndex = arr.length - 1; 45 int parentIndex = (childIndex - 1) / 2; 46 47 int temp = arr[childIndex]; 48 while (childIndex>0 && temp<arr[parentIndex]) { 49 arr[childIndex] = arr[parentIndex]; 50 childIndex = parentIndex; 51 parentIndex = (parentIndex - 1) / 2; 52 } 53 } 54 //对数组下标为pos的元素进行下沉调整,堆的范围为[0 ... n] 55 private static void downAdjust(int[] arr, int n, int pos) { 56 int temp = arr[pos]; 57 58 int parentIndex = pos; 59 int childIndex = 2 * pos + 1; 60 while (childIndex <= n) { 61 //拿到cur值较大的孩子节点 62 if (childIndex+1<=n && arr[childIndex+1]>arr[childIndex]){ 63 childIndex = childIndex + 1; 64 } 65 //如果父节点均大于等于两个孩子节点,直接跳出 66 if (temp >= arr[childIndex]) { 67 break; 68 } 69 //交换父子节点(直接赋值即可,无需交换) 70 arr[parentIndex] = arr[childIndex]; 71 parentIndex = childIndex; 72 childIndex = 2 * childIndex + 1; 73 } 74 arr[parentIndex] = temp; 75 } 76 //对数组下标为pos的元素进行下沉调整,堆的范围为[0 ... n] 77 private static void heapify(int[] arr, int n, int i) { 78 while (true) { 79 int maxPos = i; 80 if (2*i+1<=n && arr[i]<arr[i*2+1]) { 81 maxPos = 2*i + 1; 82 } 83 if (2*i+2<=n && arr[maxPos]<arr[i*2+2]) { 84 maxPos = 2*i + 2; 85 } 86 87 if (maxPos == i) { 88 break; 89 } 90 swap(arr, i, maxPos); 91 i = maxPos; 92 } 93 } 94 95} 96 97

3、优先队列

我们知道队列就是先进先出的集合,而优先队列则是按照优先级出队,分为最大优先队列(不管入队顺序,当前队列中最大元素出队,可以用大顶堆实现)和最小优先队列(不管入队顺序,当前队列中最小元素出队,可以用小顶堆实现)。每一次入队操作就是在二叉堆尾部插入元素并对其进行上浮调整,每一次出队操作就是将二叉堆堆顶元素删除,并对新的堆顶元素进行下沉调整,因此优先队列的入队操作、出队操作的时间复杂度均为O(logn)。

1public class MyPriorityQueue { 2 private int[] data; 3 private int size; 4 5 public MyPriorityQueue() { 6 //队列初始长度 7 data = new int[8]; 8 } 9 10 //上浮调整 11 private void upAdjust() { 12 int childIndex = size - 1; //最后一个元素 13 int parentIndex = childIndex / 2; //最后一个元素的父节点 14 15 int temp = data[childIndex]; //暂存需要调整的最后一个元素 16 while (childIndex > 0 && temp > data[parentIndex]) { 17 data[childIndex] = data[parentIndex]; 18 childIndex = parentIndex; 19 parentIndex = parentIndex / 2; 20 } 21 data[childIndex] = temp; 22 } 23 //下沉调整 24 private void downAdjust() { 25 int parentIndex = 0; 26 int childIndex = 1; 27 28 int temp = data[parentIndex]; //暂存需要调整的堆顶元素 29 while (childIndex < size) { 30 //如果有右孩子,则定位到较大的孩子节点 31 if (childIndex+1<size && data[childIndex+1]>data[childIndex]) { 32 childIndex = childIndex + 1; 33 } 34 //如果父节点均大于等于两个孩子节点,则直接跳出 35 if (temp >= data[childIndex]) { 36 break; 37 } 38 //交换父子节点 39 data[parentIndex] = data[childIndex]; 40 parentIndex = childIndex; 41 childIndex = 2 * childIndex + 1; 42 } 43 data[parentIndex] = temp; 44 } 45 //扩容 46 private void resize() { 47 //将队列容量翻倍 48 int newSize = this.size * 2; 49 this.data = Arrays.copyOf(this.data, newSize); 50 } 51 52 //入队 53 public void enqueue(int e) { 54 //如果队列已满,则扩容 55 if (size >= data.length) { 56 resize(); 57 } 58 data[size++] = e; 59 upAdjust(); 60 } 61 //出队 62 public int dequeue() throws Exception { 63 if (size <= 0) { 64 throw new Exception("queue is empty"); 65 } 66 67 int head = data[0]; //暂存堆顶元素 68 69 data[0] = data[--size]; //移动最后一个元素到堆顶 70 downAdjust(); 71 72 return head; 73 } 74 //判空 75 public boolean isEmpty() { 76 return size == 0; 77 } 78 //查询队列容量 79 public int getCapacity() { 80 return data.length; 81 } 82 //查询队列元素个数 83 public int size() { 84 return size; 85 } 86 //查询堆顶元素 87 public int getHead() { 88 return data[0]; 89 } 90} 91

泛型实现:

1public class MaxPQ <Key extends Comparable<Key>> { 2 private Key[] data; 3 private int size = 0; 4 5 public MaxPQ(int capacity) { 6 data = (Key[])new Comparable[capacity + 1]; 7 } 8 9 //返回当前队列中最大元素 10 public Key getMax() { 11 return data[1]; 12 } 13 //删除最大元素(出队) 14 public Key delMax() { 15 Key max = data[1]; //暂存 16 17 swap(1, size); 18 data[size] = null; 19 size--; 20 sink(1); 21 22 return max; 23 } 24 //插入元素(入队) 25 public void insert(Key e) { 26 size++; 27 data[size] = e; 28 swim(size); 29 } 30 31 //将第k个元素进行上浮调整 32 private void swim(int k) { 33 //如果上浮到堆顶就停止上浮 34 while (k>1 && less(parent(k), k)) { 35 //如果第k个元素比上层大,将它们交换 36 swap(parent(k), k); 37 k = parent(k); 38 } 39 } 40 //将第k个元素进行下沉调整 41 private void sink(int k) { 42 //如果沉到堆底就停止下沉 43 while (leftChild(k) <= size) { 44 int larger = leftChild(k); 45 if (rightChild(k)<=size && less(larger, rightChild(k))) { 46 larger = rightChild(k); 47 } 48 //如果节点k比两个孩子都大,就不用下沉 49 if (less(larger, k)) { 50 break; 51 } 52 //交换k和其较大的孩子节点 53 swap(k, larger); 54 k = larger; 55 } 56 } 57 58 //父节点 59 private int parent(int i) { 60 return i / 2; 61 } 62 //左孩子节点 63 private int leftChild(int i) { 64 return i * 2; 65 } 66 //右孩子节点 67 private int rightChild(int i) { 68 return i * 2 + 1; 69 } 70 //判断data[i]是否比data[j]小 71 private boolean less(int i, int j) { 72 return data[i].compareTo(data[j]) < 0; 73 } 74 //交换两个元素 75 private void swap(int i, int j) { 76 Key temp = data[i]; 77 data[i] = data[j]; 78 data[j] = temp; 79 } 80} 81

 

 

上一篇:冒泡排序
下一篇:插入排序

代码交流 2021