TOC
最近在学习动态规划的时候发现非常需要优先队列的的基础，所以转而先学习一下优先队列算法。这里就找了比较通用的堆来入手了解优先队列。
堆
首先这里的堆是指数据结构中的堆，和很多编程语言中的垃圾收集实现中的堆并不是一个概念。当然那个队也源自于这个数据结构中的堆。
我们使用 A 来表示一个堆 他是一个数组，并且自身持有两个属性 length = 代表整个堆的内容长度 heap-size = 代表堆中的有效队列长度 一般来说 一个队列中应该 0 <= heap-size <= length
一个堆的基本计算方法
假设我们需要计算的节点下标为 i 那么对应他的父节点 左节点 右节点的下标计算如下 parent(i) = floor() left(i) = A[2i] right(i) =
最大堆与最小堆
一个最大堆应维持除了 root 节点以外 A[parent(i)] > A[i] 相反 最小堆 A[parent(i)] <= A[i]
从用途上说，最小堆可以帮助我们完成优先队列。
维持堆的特性
这就是整个堆解构最关键的地方，如何维持一个数组保持堆的特性。
接下来是维持最大堆性质的MAX_HEAPIFY算法,同时也有通过 MAX_HEAPIFY 建造最大堆的实现。
通过修改比较部分，你也能很方便的去实现一个最小堆。
我写了一个简单的 JS 实现
const left = i => 2 * i
const right = i => 2 * i + 1
const parent = i => Math.floor(i / 2)
/**
* @param {Array} A 堆数组
* @param {number} i 处理下标
*/
function MAX_HEAPIFY(A, i) {
let l = left(i)
let r = right(i)
let cur = A[i]
let largest = i
if (l < A.headSize && cur < A[l]) {
largest = l
}
if (r < A.headSize && A[largest] < A[r]) {
largest = r
}
// 以上总结一句话 我 左 右 三个里面找最大
if (largest !== i) {
;[A[i], A[largest]] = [A[largest], A[i]] // es6语法 解构 互换值
MAX_HEAPIFY(A, largest)
}
}
// 吸收一个乱序数组构建一个最大堆
function BUILD_MAX_HEAP(A) {
A.headSize = A.length
for (let i = Math.floor(A.length / 2); i >= 0; i--) {
MAX_HEAPIFY(A, i)
}
}
let array = [5, 2, 6, 1, 6, 8, 2, 39, 2, 6, 89, 5, 6, 4, 7]
console.log(BUILD_MAX_HEAP(array))
//[89, 39, 8, 7, 6, 6, 6, 5, 2, 6, 2, 5, 2, 4, 1, headSize: 15]
值得注意的是他的构建过程是循环所有这个位置是某些节点的父节点，也就是自身是一个最大堆的子树。并且整个过程是从底部不断的向上，最后一次是运行在最上层的根节点上的，这个过程，每次循环基本不会发生递归，通常最多只要交换一次 i 与 largest 的值就可以完成运算，因为子堆已经完成排序。所以他的复杂度大约是 O(lgn) 也就是 O(h)。
接下来是依赖这两个函数的堆排序算法
function HEAP_SORT(A) {
let heap = BUILD_MAX_HEAP(A)
for (let i = A.length - 1; i >= 1; i--) {
;[A[i], A[0]] = [A[0], A[i]] // 将当前能找到第i大的值放置到i中
A.headSize = A.headSize - 1 // 减少HEAPSIZE会让MAX_HEAPIFY跳过最后面已经完成排序的部分
MAX_HEAPIFY(A, 0)
}
return A
}
循环里共循环 n 次 内部 MAX_HEAPIFY 的复杂度为lgn 所以总性能为 O(nlogn)
优先队列
虽然堆排序的性能不够出色，但是其自身的性质能够用来做很多特殊的数据结构，比如优先队列。
先来看一下一个优先队列的基本操作
insert(S,x) 插入 将元素 X 插入到集合 S 中 MAX_OR_MIN(s) 获取最大或者是最小的元素（不从 S 中删除） 具体是 MAX 还是 MIN 取决于你的需要 MAX_OR_MIN_EXT(S) 推出并返回 S 中 MAx_OR_MIN 的元素 INCREASE_KEY(S,x,k) 将某个元素的权重改成 k
以下是用上面的基本堆实现的一个最小优先队列
const left = i => 2 * i
const right = i => 2 * i + 1
const parent = i => Math.floor(i / 2)
/**
* @param {Array} A 堆数组
* @param {number} i 处理下标
*/
function MIN_HEAPIFY(A, i) {
let l = left(i)
let r = right(i)
let cur = A[i]
let minimum = i
if (l <= A.heapSize && cur.key > A[l].key) {
minimum = l
}
if (r <= A.heapSize && A[minimum].key > A[r].key) {
minimum = r
}
// 以上总结一句话 我 左 右 三个里面找最小
if (minimum !== i) {
;[A[i], A[minimum]] = [A[minimum], A[i]] // es6语法 解构 互换值
MIN_HEAPIFY(A, minimum)
}
}
function BUILD_MIN_HEAP(A) {
A.heapSize = A.length - 1
if (A.heapSize < 0) return
for (let i = Math.floor(A.heapSize / 2); i >= 0; i--) {
MIN_HEAPIFY(A, i)
}
}
const array = [
{
value: 'skfj',
key: 5
},
{
value: 'skfj2342',
key: 3
},
{
value: 'skfj111',
key: 9
},
{
value: 'skfj234346',
key: 9
},
{
value: '0',
key: 0
}
]
class Q {
constructor(arr = []) {
this.heap = arr
BUILD_MIN_HEAP(this.heap)
}
getMinimum() {
return this.heap[0]
}
extHeapMin() {
if (this.heap.heapSize < 0) {
return false
}
let min = this.heap[0]
this.heap[0] = this.heap[this.heap.heapSize]
this.heap.heapSize--
MIN_HEAPIFY(this.heap, 0)
return min
}
incrHeapKey(i, key) {
if (key < this.heap[i].key) {
return false
}
this.heap[i].key = key
// 修改权重可能会破坏本身的特性 不断向上修复这个问题。
while (i > 0 && this.heap[parent(i)].key > this.heap[i].key) {
;[this.heap[i], this.heap[parent(i)]] = [
this.heap[parent(i)],
this.heap[i]
]
i = parent(i)
}
}
insert(value) {
this.heap.heapSize++
this.heap[this.heap.heapSize] = value
this.incrHeapKey(this.heap.heapSize, value.key)
}
}
let q = new Q(array)
q.insert({
value: '我干',
key: 6
})
q.insert({
value: '我',
key: 3
})
总的来说还是挺简单的，不过非常实用。 试试我的自动同步