Shinkai005

V1

2022/02/12阅读:26主题:红绯

数据结构

image-20220212085245101
image-20220212085245101

堆是什么?

  • 堆是一种特殊的完全二叉树.

    • 完全二叉树一定是堆,但是记得堆有个传递大小的特性.也就是满足下面特性才叫堆
  • 所有的节点都大于等于子节点/小于等于它的子节点

    • 分别叫做最小堆,最大堆.

    • 根最小就是最小堆.

JS中的堆

  • JS中通常用数组表示堆

image-20211202123002274
image-20211202123002274
  • 任意节点的左侧子节点位置是2*index+1

  • 任意节点的右侧子节点位置是2*index+2

  • 父节点的位置是(index-1)/2

这个就比较奇怪, 因为这是完全二叉树的特性..还没用到堆,估计学后面就悟了

堆的应用

  • 堆能高效、快速地找出最大值和最小值,时间复杂度O(1)
  • 找出第K个最大最小值。

第K个最大元素

  • 构建一个最小堆,并将元素依次插入堆中。
    • 这里解释下,比如需要第6个元素,那么构建一个已经有6元素的堆,或者无限大也可..
  • 当堆的容量超过K,就删除堆顶。
  • 插入结束后,堆顶就是第K个最大元素

小疑问:插入的时候不是说插入就插入啊...不是要看大小插入到对应位置么..具体怎么做?

js实现最小堆类

插入

  • 将值插入堆的底部,即数组的尾部
  • 然后上移:将这个值和他的父节点进行交换,直到父节点小于等于这个插入的值
  • 大小为K的堆中插入元素的时间复杂度为O(logK);
class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i1, i2) {
        //const temp = this.heap[i1];
        //this.heap[i1] = this.heap[i2];
        //this.heap[i2] = temp;
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    getParentIndex(i) {
        return Math.floor((i - 1) / 2);
        // return (i-1) >> 1; // 老师用的是下面的,但是js位运算比mathAPi慢,所以...
    }
    shiftUp(index) {
        if (index === 0) { return; }
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }

    }
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    peek() {
        return this.heap(0);
    }
    size() {
        return this.heap.length;
    }

}
const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();
console.log(h.heap);

删除堆顶

  • 用数组的尾部元素替换堆顶(直接删除堆顶元素会破坏堆结构)
  • 然后下移:将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶
  • 大小为k的堆中删除堆顶的时间复杂度为O(logK)

获取堆顶和堆的大小

  • 获取堆顶:返回数组的头部
  • 获取堆的大小:返回数组的长度

最后写一个可读性和性能哪个优先的思想.

image-20211202215634778
image-20211202215634778

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai