数据结构-9-二叉堆-堆排序
程序猿小码 Architect

通过上一节的学习,我们了解到

  • 二叉堆的本质还是一个完全二叉树
  • 无序数组通过构造、通过下沉构造可以构造为最小堆
  • 通过上浮构造可以构造为最大堆

来说今天的堆排序算法之前、首先请和我一起、再次了解一下二叉堆元素的删除

二叉堆删除元素

这里假设我们这里有这样的一个完全二叉树如下:
image.png

1、删除顶部1号元素【暂且放到尾部】、9号元素到达顶部
image.png

2、二叉堆进行自我结构的调整、省略调整步骤、9号元素最终到达叶子节点
image.png

3、删除顶部2号元素、8号元素到达顶部。
image.png

4、二叉堆尽心自我结构的调整、省略调整步骤
image.png

5、继续删除顶部3号元素、9号元素到达顶部
image.png

我们不难发现:每次通过删除顶部的元素,通过二叉堆的自我调节、每次删除的元素呈现出有序

我们可以简单总结出:

  • 将无序的数组构造成二叉堆
  • 依次删除二叉堆顶部元素、借助二叉堆的自我调节、删除的元素呈现出有序化

这就是我们今天要整理的 堆排序

代码整理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static void sort(int[] array) {
/**
* 将无序数组调整成二叉堆
*/
buildBinaryHeap(array);

for (int i = array.length - 1; i > 0; i--) {
//删除对顶、放置到堆尾部、实则交换元素
int temp = array[0];
array[0] = array[i];
array[i] = temp;
//将堆顶部元素进行下沉
sinking(array, 0, i);
}
}

/**
* 构建二叉堆、让当前元素下沉
*
* @param array 被操作的数组
* @param itemIndex 当前元素下标
* @param length 当前二叉堆长度
*/
public static void sinking(int[] array, int itemIndex, int length) {
//父节点值
int parent = array[itemIndex];

//默认操作的是左孩子
int childIndex = 2 * itemIndex + 1;

while (childIndex < length) {

//存在右边子元素、并且右边子元素值小于左边
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
//切换到右边元素
childIndex++;
}

//小于等于则无需交换
if (parent <= array[childIndex]) break;

//无需交换、只需要将子元素移动到父元素位置即可
array[itemIndex] = array[childIndex];
itemIndex = childIndex;

//改变左右子元素的下标
childIndex = 2 * itemIndex + 1;
}
//最终将父元素移动到指定位置即可。
array[itemIndex] = parent;
}

代码只是在上一节的基础上,我们加了一个sort方法,sort 方法负责首次将无序数组整理成二叉堆、然后从尾部开始循环,将头部元素和尾部元素进行交换 ,然后将头部元素元素进行一次下沉 即可。

小结

通过本节的学习,一个数组、也可以玩出如此的花样、通过构建二叉堆、将头部元素进行删除、达到我们排序的目的。
二叉堆作为一个强大的数据结构、还是需要认真学习!

代码示例

https://gitee.com/mrc1999/Data-structure

参考

https://mp.weixin.qq.com/s/8Bid1naBLtEjPoP-R4HkBg

  • 本文标题:数据结构-9-二叉堆-堆排序
  • 本文作者:程序猿小码
  • 创建时间:2021-07-21 17:16:22
  • 本文链接:https://keep.xpoet.cn/2021/07/21/数据结构-9-二叉堆-堆排序/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论