4

数据结构-9-二叉堆-堆排序

 3 years ago
source link: https://blogs.chaobei.xyz/2021/07/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-9-%E4%BA%8C%E5%8F%89%E5%A0%86-%E5%A0%86%E6%8E%92%E5%BA%8F/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

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

二叉堆删除元素

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

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

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

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

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

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

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

我们可以简单总结出：

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

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK