优先队列 #

一种抽象数据类型，表示了一组值和对值的操作。

优先队列最重要的操作就是删除最大元素和插入元素。

初级实现 #

• 思路1：数组（无序），栈，insert时使用push，delMax时，使用选择排序思路，找到最大的和最后的元素交换，pop。
• 思路2：数组（有序），insert将所有较大的元素向右移动（插入排序思路），这样子最大的元素总会在数组的一边，delMax时，直接pop。
• 思路3：链表。修改pop，找到并返回最大元素；或者修改push，保证所有元素逆序，用pop时来删除并返回最大元素。

对于栈和队列，我们的实现能 够在常数时间内完成所有操作

而对于优先队列，插入元素和 删除最大元素这两个操作之一在最坏情况下需要线性时间来完成。

认识堆 #

在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素， 以此类推。

当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

二叉堆 #

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存(不使用数组的第一个位置)。

特点：

1. 根结点是堆有序的二叉树中的最大结点。
2. 位置 k 的结点的父结点的位置为 Math.floor(k/2) ，而它的两个子结点的位置则分别为 2k 和 2k+1。
3. 一棵大小为 N 的完全二叉树的 高度为 Math.floor(lgN)。

二叉堆的算法 #

我们使用一个长度为N + 1的私有数组来代表一个大小为 N 的二叉堆，堆元素存放在pq[1]到pd[N]的位置。

对于一个含有 N 个元素的基于堆的优先队列，插入元素操作只需不超过(lgN+1)次比较， 删除最大元素的操作需要不超过 2lgN 次比较。

索引优先队列 #

堆排序 #