图解大根堆的堆排序

2024-05-30 19:27| 来源: 网络整理| 查看: 265

文章目录 1 大根堆2 创建堆，heapInsert3 调整堆 heapify4 堆排序

1 大根堆

进行堆排序之前，需要先明确大根堆的概念，大根堆就是根节点是整棵树的最大值(根节点大于等于左右子树的最大值)，对于他的任意子树，根节点也是最大值。大根堆有两个操作，一个创建堆heapInsert时间复杂度是O(N),还有一个操作是当大根堆里的某个节点的值，发生变化的时候，需要对这个大根堆进行调整，每一次调整时间复杂度是O(lg(N))，调整的次数是跟这个堆的高度有关。这里总结了一下，使用了很多图，应该很简单就能立即

2 创建堆，heapInsert

这里堆放到数组里进行存储的，首先堆是一棵完全二叉树。比如一棵树有N个元素，存放在数组里分别对应0~N-1，假设数组中从0到i-1位置的元素是一个大根堆，然后把第i个位置的元素插入大根堆里，构造一个新的大根堆，就需要从第i个位置的元素开始，依次看它的父节点的值是否小于它，如果小于就进行交换，直到它的父节点不小于它，或者到了该大根堆的最顶端的根节点，这一次过程才算彻底结束。上面说的不太清楚，看下面具体的例子下面这个是一个随机生成的数组。在这里插入图片描述它对应的完全二叉树的结构： index是数组的下标，从0开始，现在开始创建大根堆，index=0；

大根堆结构数组

index=1 把43插入到大根堆里，43的父节点为9，43大于9，所以9要和43交换位置，然后构成新的大根堆。

大根堆结构数组

index=2 把-54插入进来，由于-54小于它的父节点43，所以不进行交换

大根堆结构数组

index=3 插入4，由于4小于它的父节点，所以不进行交换。

大根堆结构数组

index=4 插入-13，由于-13小于它的父节点，所以不交换。

大根堆结构数组

index=5 插入10，由于10比它的父节点-54大，所以进行交换。

大根堆结构数组

index=6 插入36，36比它的父节点10大，进行交换

大根堆结构数组

以上就是建立整个大根堆的过程。

public static void heapInsert(int[] arr,int index){ /* 对第i个元素进行插入，前提是前i-1个元素已经变成了大根堆，然后把最后面的一个元素，插入进去，进行调整，把它变成大根堆，它调整的过程是看第i个元素的父节点，是否比它小，如果小的话，就进行交换，然后再网上看父节点，直到它的父节点比他大，或者到了整棵树的根节点。 * */ while(arr[index]>arr[(index-1)/2]){ // while 循环的终止条件是当前节点比它的父节点小，当index为0的时候，(index-1)/2也为0，循环也会终止。 swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } // swap函数用于交换两个不同位置的元素 public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } 3 调整堆 heapify

数组中对应的大根堆的长度为heapSize,则从0到heapSize-1,是大根堆里的元素，当数组中下标为index的元素的值发生了变化，就要对这个堆进行调整，保证它还是大根堆，具体过程是：将index对应的元素和它的左右子节点的值进行比较，如果比它小的话，就把index对应的元素和它的左右子节点中最大的值进行交换，交换后对他的子节点也执行这个过程。

public static void heapify(int[] arr,int index,int heapSize){ // 要调整的节点的左孩子节点 int left=2*index+1; // 0到heapSize-1,是大根堆，所以当left等于或者大于heapSize的时候，说明index对应的节点就是叶子节点。 while(left break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } }

以上面的大根堆为例，我们最上面的元素43和最后面的一个元素交换，同时把heapSize减1，这个时候数组就变成了这样：在这里插入图片描述这个数组对应的堆就变成了这样：43 不考虑。接下来开始进行调整，首先是10和它的左右子元素进行比较，36比较大，交换。就变成了这样：然后10比-54大，所以不用再进行交换了，这就是一次heapify.

4 堆排序

堆排序就是利用了heapinsert和heapify来进行排序，当创建完大根堆以后，每一次都把堆顶的元素和堆的最后一个元素进行交换，并且把堆的长度减小1，然后对新的堆进行调整，重新调整为大根堆，然后再取堆顶的元素和堆的最后一个节点进行交换，大根堆的长度减小1，然后再调整，重复这个过程，直到堆里面剩余的元素个数为1.这就是堆排序，具体代码如下：

public static void heapSort(int[] arr) { if (arr == null || arr.length heapInsert(arr, i); } int size = arr.length; swap(arr, 0, --size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

还是以上面的数组对应的大根堆为例：最开始：在这里插入图片描述刚开始heapSize 为7，把43 和10 进行交换，heapSize变成6，此时堆对应的数组就变成了然后开始调整：10 和36交换，堆对应的数组就变成了左边这个，由于10不小于-54，不再进行交换，这个时候43 不考虑。

把36和-54 交换，heapSize变成5，最开始的时候是最左边，然后-54和10进行交换，因为heapSize为5，这一次就结束了。