什么是堆排序

阅读原文

理解堆排，首先要理解二叉堆。理解了二叉堆的“下沉”操作，基本上就可以理解堆排了。今天我们来看一看什么是堆，以及堆的一般操作

优先级队列

近日，谦子遇到了烦心事，于是找老师去诉苦了

1.png

谦子列了几个要做的事

2.png
谦子道出了心中的苦
3.png

谦子两眼发光

4.png
克顺手画了一个图
5.png

优先级队列中每个元素都有优先级优先级最高的最先被处理

优先队列的实现

6.png

谦子非常想知道黑盒里面是什么

7.png

克非常善于引导学生思考

8.png
谦子想了想说
10.png
谦子说着说着画了一个图
11.png

谦子画了一幅图解释道

12.png
随后，谦子又画出了插入6后的图
13.png
克还是不满意
14.png

堆

15.png

这里我们只讨论二叉堆，把二叉堆称为堆
堆也有d-堆，左式堆等等

16.png

克看谦子不是很明白，顺手画了个图

17.png

克画了一个二叉堆实例

18.png

注意：二叉堆中两个孩子之前的大小没有关系，可能左孩子>=右孩子，也可能右>=左

19.png

克随手画了一个小根堆和一个大根堆

20.png
21.png
22.png

插入操作

23.png

每个父节点的值小于等于其左右孩子的值被称为堆的有序性
另一种情况是大于等于也称之为堆的有序性

克随手画了一个插入操作破坏堆有序性的图

24.png

如何调整，谦子心里想

25.png
上浮这个词形象生动，谦子心里想
26.png

说完，克飞速地写出了上浮的代码

/**
* 如果待插入的元素小于其父，则交换子和父，并继续上浮，直到大于等于其父
* @param arr 储存堆的数组，元素从下标1开始有效，0位置不存在有效值
* @param inserted 被插入节点的索引
*/
public void swim(int[] arr, int inserted) {
    int parent = inserted/2;
    if (arr[inserted] < arr[parent]) {
        swap(arr, inserted, parent);
        swim(arr, parent);
    }
}

谦子暗自惊叹老师的代码功力

删除操作

29.png

谦子听完此话紧张的手心出汗，但还是硬着头皮想了想，突然灵光一现

30.png

随后谦子画出了交换后的图

31.png
32.png
33.png
34.png
35.png

谦子刚松了口气，谁知还要写代码，只见谦子想了想，写写擦擦好几遍最终写下了如下代码

/**
* 对以arr[parentIndex]为父节点的堆进行调整（下沉）
* 在父节点，左右孩子中选出最小的节点，如果最小节点不是父节点则交换
* 继续下沉，反之不下沉
* @param arr 要调整的数组
* @param parentIndex 父节点的索引
*/
public void sink(int[] arr, int parentIndex) {
    // 堆的大小，第0 个位置无有效值
    int heapSize = arr.length - 1;
    // 从父节点，左孩子和右孩子选出最小节点，得其索引
    int minNodeIndex = minIndex(arr, parentIndex, heapSize);
    // 如果最小的节点的索引不是父节点，则说明最小的节点在左右孩子中，交换并继续下沉调整
    if (minNodeIndex != parentIndex) {
        swap(arr, minNodeIndex, parentIndex);
        sink(arr, minNodeIndex);   // 交换后继续下沉
    }
}

36.png

慧子解释道，并画了一个图

37.png

只见谦子又写了一段代码

/**
* 求得给定的三个节点的最小节点的索引
* @param parentIndex 父节点的索引
* @param heapSize 堆的大小
* @return 最小节点的索引
*/
private int minIndex(int[] arr, int parentIndex, int heapSize) {
    int minIndex = parentIndex; // 保存最小节点的下标，初始时认为父节点最小
    int leftIndex = leftIndex(parentIndex);  // 找到parent的左孩子下标
    // 如果leftIndex没有越界，比较左孩子和父节点，选择小的Node的下标赋给minIndex
    if (leftIndex <= heapSize) {
        minIndex = arr[leftIndex] < arr[parentIndex] ? leftIndex : parentIndex;
    }
    int rightIndex = rightIndex(parentIndex);
    if (rightIndex < heapSize) {
        minIndex = arr[rightIndex] < arr[minIndex] ? rightIndex : minIndex;
    }
    return minIndex;
}

leftIndex = 2parentIndex;
rightIndex = 2parentIndex+1;

40.png

看来以后得好好学数据结构与算法了，不然连时间都管理不好，谦子心想
摘录自：码分享