堆（Heap）

• 李艳生
• 湖北师范大学
• 物理与电子科学学院
• 2020年春季

回顾

• 树（父子关系的节点集合）
• 二叉树（最多只有两个子节点）
• 二叉搜索树（左子节点<节点<右子节点）
• AVL树(节点左右子树高度最多相差1)
• 红黑树(两个红色节点不能相邻)

引入

• 一棵二叉树的结点要么是叶子结点，要么它有两个子结点
• 如果一个二叉树的层数为K，且结点总数是2^K-1，则它就是满二叉树。

满二叉树

引入

• 除了最后一层的叶节点外，树的每一层都有左侧和右侧子节点，并且最后一层叶节点连续集中在最左边
• 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边

完全二叉树

二叉堆的概念

• 二叉堆是一个完全二叉树。
• 二叉堆两种类型：最大堆和最小堆

最大堆

• 所有的节点都大于等于每个它的子节点
• 根节点即为最大值

最小堆

• 所有的节点都小于等于每个它的子节点
• 根节点即为最小值

堆操作

• 建堆
• 插入
• 删除
• 访问

建堆

• 用数组表示堆

class MinHeap {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.heap = [];
  }
  insert(value){} //插入
  peek(){} //访问根结点
  poll(){} //移除根结点，并返回根节点
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

建堆

访问节点

• 对于给定位置index的节点
  • 它的左侧子节点的位置是2 * index + 1（如果位置可用）；
  • 它的右侧子节点的位置是2 * index + 2（如果位置可用）；
  • 它的父节点位置是（index - 1） / 2（如果位置可用）

访问节点

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);
}

辅助方法

size() {
    return this.heap.length;
}
isEmpty() {
    return this.size() <= 0;
}
clear() {
    this.heap = [];
}
swap(a, b) {
    /* const temp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = temp; */
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}

插入

• 先将值插入堆的底部叶节点(数组的最后一个位置)
• 再将这个值和它的父节点进行交换，直到父节点小于这个插入的值

插入

insert(value) {
  if (value != null) {
    const index = this.heap.length;
    this.heap.push(value);
    this.siftUp(index); //上移堆化
    return true;
  }
  return false;
}

上移堆化

siftUp(index) {
  let parent = this.getParentIndex(index);
  while (
    index > 0
    && this.compareFn(this.heap[parent], 
    this.heap[index]) === Compare.BIGGER_THAN
  ) {
    swap(parent, index);
    index = parent;
    parent = this.getParentIndex(index);
  }
}

插入使用

const heap = new MinHeap();

heap.insert(2); 
heap.insert(3); 
heap.insert(4); 
heap.insert(5); 

heap.insert(1);

插入使用

访问根结点

peek() {
    return this.isEmpty() ? undefined : this.heap[0];
}

删除根结点

• 移除数组中的第一个元素（堆的根节点）
• 将堆的最后一个元素移动至根部,交换元素直到堆的结构正常

删除根结点

poll() {
  if (this.isEmpty()) {
    return undefined;
  }
  if (this.size() === 1) {
    return this.heap.shift();
  }
  const removedValue = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.siftDown(0);//下移堆化
  return removedValue;
}

下移堆化

siftDown(index) {
  let element = index;
  const left = this.getLeftIndex(index);
  const right = this.getRightIndex(index);
  const size = this.size();
  if (
    left < size
    && this.compareFn(this.heap[element], 
    this.heap[left]) === Compare.BIGGER_THAN
  ) {
    element = left;
  }
  if (
    right < size
    && this.compareFn(this.heap[element], 
    this.heap[right]) === Compare.BIGGER_THAN
  ) {
    element = right;
  }
  if (index !== element) {
    swap(index, element);
    this.siftDown(element);
  }
}

删除根节点

最大堆

class MaxHeap extends MinHeap {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = reverseCompare(compareFn);
  }
}

function reverseCompare(compareFn) {
  return (a, b) => compareFn(b, a);
}

最大堆使用

const maxHeap = new MaxHeap();

maxHeap.insert(2);
maxHeap.insert(3)
maxHeap.insert(4);
maxHeap.insert(5);

maxHeap.insert(1);
console.log('Heap size: ', maxHeap.size()); // 5 
console.log('Heap min value: ', maxHeap.peek()); // 5

堆排序

• 创建一个最大堆或最小堆
• 将数组中元素依次插入堆中
• 删除根结点，并将返回根节点插入返回数组，直到堆为空

堆排序

堆排序

function sort(originalArray) {
    const sortedArray = [];
    const minHeap = new MinHeap();

    // Insert all array elements to the heap.
    originalArray.forEach((element) => {
      minHeap.insert(element);
    });

    while (!minHeap.isEmpty()) {
      const nextMinElement = minHeap.poll();
      sortedArray.push(nextMinElement);
    }
    return sortedArray;
  }

任务

请用堆排序算法将数组[9, 8, 7, 6, 5, 4, 3, 2, 1]按升序排序。