堆

2021-12-01 本文已影响0人 sweetBoy_9126

1. 是什么

一种特殊的完全二叉树。（完全二叉树：每层节点完全填满，最后一层若不完全填满，则只缺少右侧部分的节点）
比如：
所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。
js 中通常用数组表示堆。

上面红色标记的012345就是它的索引值
左侧子节点的位置是 2 * index + 1
比如：根节点index是0， 2 * 0 + 1 是1，所以左侧子节点位置是1，3对应的左侧子节点的位置是 2 * 1 + 1 是3 ；6这个元素对应左侧子节点的位置是 2*2+1 是 5
右侧子节点的位置是 2 * index + 2。
比如：1的右侧节点 2 * 0 + 2 = 2；3的右侧节点是 2 * 1 + 2 = 4
父节点位置是 (index - 1) / 2的商
比如：5的父节点位置是 (3-1)/2=1；9的父节点是(4-1)/2 = 1

1.1 二叉堆的操作

1.1.1 插入节点

当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。例如插入一个新节点，值是 0。

这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新节点“上浮”，和父节点交换位置。

继续用节点0和父节点3做比较，因为0小于3，则让新节点继续“上浮”。

继续比较，最终新节点0“上浮”到了堆顶位置。

1.1.2 删除节点

二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。

这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。

接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。

继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续“下沉”。

2. 堆的应用

堆能高效、快速的找出最大值和最小值，时间复杂度：O(1)。
找出第 K 个最大（小）元素。

2.1. 最小堆类

实现步骤

在类里，声明一个数组，用来装元素。
主要方法：插入、删除堆顶、获取堆顶、获取堆大小。

插入

将值插入堆的底部，即数组的尾部。
然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值。
大小为 k 的堆中插入元素的时间复杂度为 O(logk)

class MinHeap {
  constructor() {
    this.heap = []
  }
  getParentIndex(i) {
    return Math.floor((i-1)/2);
  }
  swap(parentIndex, index) {
    const temp = this.heap[parentIndex];
    this.heap[parentIndex] = this.heap[index];
    this.heap[index] = temp;
  }
  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)
  }
}
const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1)

删除堆顶

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

shiftDown(index) {
    const leftChildIndex = this.getLeftChildrenIndex(index);
    const rightChildIndex = this.getRightChildrenIndex(index);
    if (this.heap[leftChildIndex] < this.heap[index]) {
      this.swap(index, leftChildIndex);
      this.shiftDown(leftChildIndex);
    }
    if (this.heap[rightChildIndex] < this.heap[index]) {
      this.swap(index, rightChildIndex);
      this.shiftDown(rightChildIndex);
    }
  }
pop() {
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }

获取堆顶和堆的大小
获取堆顶：返回数组的头部。
获取堆的大小：返回数组的长度。

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

2.2. 数组中的第 K 个最大元素 leetCode 215

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题思路

看到“第 K 个最大元素”
考虑使用最小堆。

解题步骤

构建一个最小堆，并依次把数组的值插入堆中。
当堆的容量超过 K，就删除堆项。

var findKthLargest = function(nums, k) {
    const minHeap = new MinHeap();
    nums.forEach(num => {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    })
    return minHeap.peek();
};

时间复杂度 O(n * logK) 因为for循环里嵌套了 insert ，insert 的复杂度是 logk，空间复杂度数组里维护了一个k的长度的堆，所以是 O(k)

2.3. 前 K 个高频元素 leetCode 347

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

方法1：用字典

var topKFrequent = function(nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    })
    return Array.from(map).sort((a, b) => b[1] - a[1]).slice(0, k).map(n => n[0])
};

时间复杂度：使用 sort 排序的时间复杂度最优的情况下是 O(n log n)，所以我们的时间复杂度是 O(n log n)
方法2：最小堆

class MinHeap {
  constructor() {
    this.heap = []
  }
  getParentIndex(i) {
    return Math.floor((i-1)/2);
  }
  getLeftChildrenIndex(i) {
    return 2 * i + 1;
  }
  getRightChildrenIndex(i) {
    return 2 * i + 2;
  }
  swap(parentIndex, index) {
    const temp = this.heap[parentIndex];
    this.heap[parentIndex] = this.heap[index];
    this.heap[index] = temp;
  }
  shiftUp(index) {
    if (index === 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex]?.value > this.heap[index].value) {
      // 交换顺序
      this.swap(parentIndex, index)
      // 递归往上查找
      this.shiftUp(parentIndex)
    }
  }
  shiftDown(index) {
    const leftChildIndex = this.getLeftChildrenIndex(index);
    const rightChildIndex = this.getRightChildrenIndex(index);
    if (this.heap[leftChildIndex] && this.heap[leftChildIndex].value < this.heap[index].value) {
      this.swap(index, leftChildIndex);
      this.shiftDown(leftChildIndex);
    }
    if (this.heap[rightChildIndex] && this.heap[rightChildIndex].value < this.heap[index].value) {
      this.swap(index, rightChildIndex);
      this.shiftDown(rightChildIndex);
    }
  }
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  peek() {
    return this.heap[0];
  }
  size() {
    return this.heap.length;
  }
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    })
    const heap = new MinHeap();
    map.forEach((value, key) => {
        heap.insert({ value, key });
        if (heap.size() > k) {
            heap.pop();
        }
    })
    return heap.heap.map(h => h.key)
};

时间复杂度：map是 O(n)里面嵌套了 insert 和 pop 的复杂度是 O(logk)，所以时间复杂度是 O(n log k) 因为 k 小于 o所以时间复杂度比第一种低
空间复杂度有一个map最差情况下是 O(n)

2.4. 合并 K 个升序链表 leetCode 23

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解题思路：

解题步骤：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
 class MinHeap {
  constructor() {
    this.heap = []
  }
  getParentIndex(i) {
    return Math.floor((i-1)/2);
  }
  getLeftChildrenIndex(i) {
    return 2 * i + 1;
  }
  getRightChildrenIndex(i) {
    return 2 * i + 2;
  }
  swap(parentIndex, index) {
    const temp = this.heap[parentIndex];
    this.heap[parentIndex] = this.heap[index];
    this.heap[index] = temp;
  }
  shiftUp(index) {
    if (index === 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex]?.val > this.heap[index]?.val) {
      // 交换顺序
      this.swap(parentIndex, index)
      // 递归往上查找
      this.shiftUp(parentIndex)
    }
  }
  shiftDown(index) {
    const leftChildIndex = this.getLeftChildrenIndex(index);
    const rightChildIndex = this.getRightChildrenIndex(index);
    if (this.heap[leftChildIndex]?.val < this.heap[index]?.val) {
      this.swap(index, leftChildIndex);
      this.shiftDown(leftChildIndex);
    }
    if (this.heap[rightChildIndex]?.val < this.heap[index]?.val) {
      this.swap(index, rightChildIndex);
      this.shiftDown(rightChildIndex);
    }
  }
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1)
  }
  pop() {
    if (this.size() === 1) return this.heap.shift();
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return top;
  }
  peek() {
    return this.heap[0];
  }
  size() {
    return this.heap.length;
  }
}
var mergeKLists = function(lists) {
    const res = new ListNode(0);
    let p = res;
    const h = new MinHeap();
    lists.forEach(l => {
        if (l) {
            h.insert(l)
        }
    });
    console.log(h.heap)
    while(h.size()) {
        const n = h.pop();
        // 把新的链表的头的下一项放到堆里继续比较
        if (n.next) h.insert(n.next)
        p.next = n;
        p = p.next
    }
    return res.next;
};

堆