优先队列和堆

什么是优先队列？

听这个名字就能知道，优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的；在有些情况下，可能需要找到元素集合中的最小或者最大元素，可以利用优先队列ADT来完成操作，优先队列ADT是一种数据结构，它支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作（返回并删除最大元素）；

这些操作等价于队列的enQueue和deQueue操作，区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列（即总是先删除最大的元素）；由于这两种类型时对称的，所以只需要关注其中一种，如升序优先队列；

优先队列ADT 

下面操作组成了优先队列的一个ADT；

1.优先队列的主要操作
优先队列是元素的容器，每个元素有一个相关的键值；

• insert(key, data)：插入键值为key的数据到优先队列中，元素以其key进行排序；
• deleteMin/deleteMax：删除并返回最小/最大键值的元素；
• getMinimum/getMaximum：返回最小/最大剑指的元素，但不删除它；

2.优先队列的辅助操作

• 第k最小/第k最大：返回优先队列中键值为第k个最小/最大的元素；
• 大小（size）：返回优先队列中的元素个数；
• 堆排序（Heap Sort）：基于键值的优先级将优先队列中的元素进行排序；

优先队列的应用

• 数据压缩：赫夫曼编码算法；
• 最短路径算法：Dijkstra算法；
• 最小生成树算法：Prim算法；
• 事件驱动仿真：顾客排队算法；
• 选择问题：查找第k个最小元素；
• 等等等等....

优先队列的实现比较

实现	插入	删除	寻找最小值
无序数组	1	n	n
无序链表	1	n	n
有序数组	n	1	1
有序链表	n	1	1
二叉搜索树	logn(平均)	logn(平均)	logn(平均)
平衡二叉搜索树	logn	logn	logn
二叉堆	logn	logn	1

---

堆和二叉堆

什么是堆

堆是一颗具有特定性质的二叉树，堆的基本要求就是堆中所有结点的值必须大于或等于（或小于或等于）其孩子结点的值，这也称为堆的性质；堆还有另一个性质，就是当 h > 0 时，所有叶子结点都处于第 h 或 h - 1 层（其中 h 为树的高度，完全二叉树），也就是说，堆应该是一颗完全二叉树；

二叉堆

在二叉堆中，每个结点最多有两个孩子结点，在实际应用中，二叉堆已经足够满足需求，因此接下来主要讨论二叉最小堆和二叉最大堆；

堆的表示：在描述堆的操作前，首先来看堆是怎样表示的，一种可能的方法就是使用数组，因为堆在形式上是一颗完全二叉树，用数组来存储它不会浪费任何空间，例如下图：

 

用数组来表示堆不仅不会浪费空间还具有一定的优势：

左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

 

 

堆排序流程

1.一趟堆排序

以数组int n[] = { 6, 5, 2, 7, 3, 9, 8 }为例：

步骤

一、构建最大堆：

从最后一个非叶子节点（计算公式为n.length/2-1,可自行验证)开始，从后往前进行调整构建，调整的规则是：若子节点大于父节点，则将子节点中较大的节点元素与父节点交换。

1.调整节点2（数组索引2），对比子节点9和8，将9和8进行交换；

2.调整节点5（数组索引1），对比子节点7和3，将7和5进行交换；

 

3.调整节点6（素组索引0），对比子节点7和9，将6和9进行交换；

二、取出最大堆数组的第一位根元素与数组末位元素交换：

2.循环构建最大堆

根据上述构建最大堆的原理可以得出堆排序的完整过程

第1趟堆排序：

第2趟堆排序：

第3趟堆排序：

第4趟堆排序：

第5趟堆排序：

第6趟堆排序：

代码实现

public class Test {

    public static void main(String[] args) {
        int n[] = { 6, 5, 2, 7, 3, 9, 8 };
        heapsort(n);
        System.out.print("堆排序结果：");
        for (int m : n) {
            System.out.print(m + " ");
        }
    }

    /**
     * 堆排序
     * @param n 待排序数组
     */
    public static void heapsort(int n[]) {
        for (int i = n.length - 1; i >= 1; i--) {
            buildHeap(n, i);
            swap(n, 0, i);
        }
    }

    /**
     * 
     * @param n   待排序数组
     * @param end 待排序数组末位下标
     */
    public static void buildHeap(int n[], int end) {
        int len = end + 1;
        for (int i = len / 2 - 1; i >= 0; i--) {
        //堆中i节点对应的左右子节点l和r
            int l = 2 * i + 1, r = l + 1;
        //指向较大数节点的指针
            int p = l;
            if (r <= len - 1 && n[l] < n[r]) {
                p = r;
            }
            if (n[i] < n[p]) {
                swap(n, i, p);
            }
        }
    }

    /**
     * 
     * @param n 待排序数组
     * @param i 待交换数字数组下标
     * @param j 待交换数字数组下标
     */
    private static void swap(int n[], int i, int j) {
        n[i] ^= n[j];
        n[j] ^= n[i];
        n[i] ^= n[j];
    }

 结果

堆排序结果：2 3 5 6 7 8 9 

一、heapsort堆排序方法
for循环（注意循环次数比数组长度小1，原因最低2个数构成最大堆）
i.根据数组长度构建最大堆；
ii.交换数组首位（最大堆根节点）与数组末位；

二、buildHeap构建最大堆
1.声明数组长度len；
2.for循环从最后一个非叶子结点开始往回遍历到根节点;
 i.找到当前非叶子结点的左右子节点下标；
 ii.声明较大数指针，默认指向左子节点；
 iii.对比左右子节点，若右子节点存在且右大于左则指向右子节点；
 iv.对比交换较大的子节点和父节点。