数据结构 | 大小顶堆（JS实现）

Posted on Edited on In Symbols count in article: 3.3k Reading time ≈ 3 mins.

基础

谈谈堆排序，大顶堆，小顶堆？

大顶堆：每个子节点都要大于等于父节点

小顶堆：每个子节点都要小于等于父节点

注意：区分大小顶堆和二叉搜索树的区别

构造小大顶堆

1. 创建小顶堆

二叉树有两种表示方法，（1）指针法；（2）索引法。这里我们使用索引法，即用数组表示堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    // 后面涉及节点交换，所以提前接好交换函数
    swap(nums, a, b) {
        [nums[a], nums[b]] = [nums[b], nums[a]];
    }
    
    // 后面涉及比较，所以提前定义好比较函数
    compare(a, b) {
        if (a < b) {
            return -1;
        } else if (a > b) {
            return 1;
        } else {
            return 0;
        }
    }
}

2. 设置访问节点的方法

要访问使用普通数组的二叉树节点，可以通过下列方式操作index

对于给定位置index节点：

  • 它的左侧节点的位置是2*index+1（如果存在）
  • 它的右侧节点的位置是2*index+2（如果存在）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 左侧节点
getLeftIndex(index) {
    return 2*index+1;
}

// 右侧节点
getRightIndex(index) {
    return 2*index+2;
}

// 父节点
getParentIndex(index) {
    if (index === 0) {
        return undefined;
    }
    return Math.floor((index-1)/2);
}

因此，可以实现堆中的三个操作：

  • insert(value)：插入值，插入成功返回true，否则返回false
  • extract()：移除最小值（小顶堆）或者最大值（大顶堆），并且返回这个值
  • findMinimum()：返回最小值（小顶堆）或者最大值（大顶堆），并且不会移除这个值

3. 插入值

插入值的操作流程：

  1. 将值插入堆的底部节点
  2. 执行siftUp方法，表示将这个值和它的父节点进行交换，直到父节点小于这个插入的值——上移操作
1
2
3
4
5
6
7
8
9
insert(value) {
    if (value !== null) {
        this.heap.push(value);  // step1:插入值
    	// this.heap.length - 1 即为新插入元素的index（索引）
    	this.siftUp(this.heap.length - 1);  // step2:执行siftUp方法
    	return true;
    }
    return false;
}
上移操作siftUp

步骤：

  • 获取父节点parentIndex
  • 比较节点value与父节点value的大小交换节点
  • 递归，递归结束条件：index > 0 并且 this.heap[index] > this.heap[parentIndex]
1
2
3
4
5
6
7
8
9
siftUp(index) {
    let parentIndex = this.getParentIndex(index);
    while (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) > -1) {
        this.swap(this.heap, index, parentIndex);      // 交换
        // 递归
        index = parentIndex;
        parentIndex = this.getParentIndex(index);
    }
}

4. 从堆中找到最小值

在最小堆中，最小值永远位于堆顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 堆长度
size() {
    return this.heap.length;
}

// 堆是否为空
isEmpty() {
    return this.heap.length === 0;
}

// 空即为undefined，不为空返回堆顶元素
findMinimum() {
    return this.isEmpty ? undefined : this.heap[0];
}

5. 移除小顶堆中的最小值

移除值的操作流程：

  1. 两个特殊情况
    • 堆为空，直接返回undefined
    • 堆size为1，返回并移除堆顶元素，不需要其他操作
  2. 其他情况：
    • 移除堆顶元素
    • 重新调整堆结构——下移操作
1
2
3
4
5
6
7
8
9
10
11
12
extract() {
    if (this.isEmpty) {
        return undefined;
    }
    
    if (this.size() === 1) {
        return this.heap.shift();
    }
    
    const removeValue = this.heap.shift();   // 获取要移除的节点的value
    this.shiftDown(0);
}
下移操作（堆化）

整个过程可以抽象为：将堆的最后一个元素移动至根部并执行siftDown函数，执行交换函数直至堆结构正常

步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
siftDown(index) {
    let element = index;
    
    // 获取左右子节点的index
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();
    
    // 节点比较，确定是否需要交换
    if (left < size && this.compare(this.heap[element], this.heap[left]) > -1) {
        element = left;
    }
    
    if (right < size && this.compare(this.heap[element], this.heap[right]) > -1) {
        element = right;
    }
    
    // 判断值和传入element是否相同，和自己交换是没有意义的
    if (index !== element) {
        this.swap(this.heap, index, element);
        this.siftDown(element);   // 递归此操作
    }
}

构造大顶堆

大顶堆和小顶堆的算法一模一样，不同之处在于大小比较

堆排序算法

思路/步骤

  • 数组构造成一个堆（根据实际需求创建大顶堆或者小顶堆），以小顶堆为例
  • 在创建大顶堆后，最大值会被存储在堆的第一个位置，我们要将它替换为堆的最后一个值，将堆的大小减1
  • 最后，将堆的根节点下移并且重复步骤2直到堆的大小为1

堆排序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function heapSort(arr) {
    let heapSize = arr.length;
    buildMaxHeap(arr);
    while (heapSize > 1) {
        swap(arr, 0, --heapSize);
        heapify(arr, 0, heapSize);
    }
    return arr;
}


// 构建最大堆
function buildMaxHeap(arr) {
    for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    return arr;
}

参考

大顶堆/小顶堆的构建以及排序的应用

图解大顶堆的构建、排序过程

谈谈堆排序，大顶堆，小顶堆？