作者丨gyl_coder

https://www.jianshu.com/p/501383fb1671

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

优先级队列

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

谦子列了几个要做的事

谦子道出了心中的苦

谦子两眼发光

克顺手画了一个图

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

优先队列的实现

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

克非常善于引导学生思考

谦子想了想说

谦子说着说着画了一个图

谦子画了一幅图解释道

随后，谦子又画出了插入6后的图

克还是不满意

堆

这里我们只讨论二叉堆，把二叉堆称为堆

堆也有d-堆，左式堆等等

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

克画了一个二叉堆实例

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

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

插入操作

每个父节点的值小于等于其左右孩子的值被称为堆的有序性

另一种情况是大于等于也称之为堆的有序性

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

如何调整，谦子心里想

上浮这个词形象生动，谦子心里想

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

/**

* 如果待插入的元素小于其父，则交换子和父，并继续上浮，直到大于等于其父* @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);    }}

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

删除操作

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

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

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

/**

* 对以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);   // 交换后继续下沉    }}

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

只见谦子又写了一段代码

/**

* 求得给定的三个节点的最小节点的索引* @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;

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