[数据结构] 堆与堆排序

这篇文章使用 JavaScript 语言进行相关代码的编写。

数据结构——堆 heap

基本概念与性质

堆是一颗完全二叉树,根据父子节点之间值的大小关系可以分为:

  • 大根堆:每一个节点的值 大于或等于 其子节点的值;
  • 小根堆:每一个节点的值 小于或等于 其子节点的值;

堆数据结构的底层通常使用顺序表进行存储。

通过索引的计算可以快速得到子节点、父节点的值:

以 0 作为根节点的索引:(下文使用这种标准)

Parent(i) = (i-1)/2;
LeftChild(i) = i*2+1;
RightChild(i) = i*2+2;

以 1 作为根节点的索引

Parent(i) = i/2;
LeftChild(i) = i*2;
RightChild(i) = i*2+1;

操作

一开始堆是一个空数组,最主要的两个API是插入和删除,这两个操作会在堆的头部和尾部进行操作,而这些操作会导致堆的性质丢失,因此每次进行插入和删除操作之后都需要重新维护堆的结构。

插入

插入操作将一个新的数据添加到堆的末尾,然后向上调整

图片来源:二叉堆 - OI Wiki (oi-wiki.org)

删除

删除操作将根节点摘除,然后将堆的末尾的节点移动到堆的顶部,最后向下调整

向上调整

对于某个节点(由一个明确的索引i指定),通过计算得到它的父节点的值,进行比较:

  • 如果二者大小不满足堆性质,则交换(即上升),上升后继续与新的父节点进行比较;
  • 如果二者大小满足堆性质,则终止。

时间复杂度与树的高度有关,这是完全二叉树,即O(log N)

function up(index){
  while(true){
    const parent = (index-1)>>1;
    if(this.arr[parent] < this.arr[index]){
      [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
      index = parent;
    }else{
      break;
    }
  }
}
  • (index-1)>>1是通过位运算快速实现向下取整的除以2,有时候懒得写Math.floor...

向下调整

对于某个节点,通过索引计算得到左右两个子节点,分别进行比较:(以小根堆为例)

  • 如果当前节点的值均小于左右两个子节点的值,则说明满足堆结构,终止;
  • 如果左右两个子节点存在小于当前节点的值,那么找出最小值,最小的节点与当前节点进行交换(即下沉),下沉后继续与新的左右子节点进行比较。

时间复杂度:O(log N)

function down(index){
  while(true){
    let left = index*2+1;
    let right = index*2+2;
    let target = index;
    if(left<this.size() && this.arr[left]>this.arr[index]){
      target = left;
    }
    if(right<this.size() && this.arr[right]>this.arr[index]){
      target = right;
      if(left<this.size() && this.arr[left]>this.arr[right]){
        target = left;
      }
    }
    if(target!==index){
      [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
      index = target;
    }else{
      break;
    }
  }
}

完整代码

class Heap {
  constructor(arr) {
    if(arr){
      this.arr = arr;
      for(let i=Math.floor((arr.length-1)/2); i>=0; i--){
        this._down(i);
      }
    }else{
      this.arr = [];
    }
  }

  size() {
    return this.arr.length;
  }

  push(val) {
    // 新的数据插入到尾部,然后向上调整
    this.arr.push(val);
    this._up(this.size() - 1);
  }

  top() {
    return this.arr[0];
  }

  pop() {
    // 没有数据了,返回null
    if (this.size() == 0) return null;
    // 只剩下一个数据了,直接弹出返回
    if(this.size() == 1)return this.arr.pop();
    // 先记录堆顶数据
    let top = this.top();
    // 将最后一个数据放到堆顶,然后向下调整
    let last = this.arr.pop();
    this.arr[0] = last;
    this._down(0);
    return top;
  }

  _up(index){
    while(true){
      const parent = (index-1)>>1;
      if(this.arr[parent] < this.arr[index]){
        [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
        index = parent;
      }else{
        break;
      }
    }
  }

  _down(index){
    while(true){
      let left = index*2+1;
      let right = index*2+2;
      let target = index;
      if(left<this.size() && this.arr[left]>this.arr[index]){
        target = left;
      }
      if(right<this.size() && this.arr[right]>this.arr[index]){
        target = right;
        if(left<this.size() && this.arr[left]>this.arr[right]){
          target = left;
        }
      }
      if(target!==index){
        [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
        index = target;
      }else{
        break;
      }
    }
  }
}

堆排序

堆排序是建立在堆这种数据结构上的选择排序。

首先建立大根堆,每次从根节点获取最大值,将最大值移动到堆的尾部,然后对剩下的前n-1个节点进行维护大根堆的操作。

即:每次选择最大值移动至尾部,再继续在剩下的数中继续查找最大值。

  • 普通的选择排序是在线性表上寻找最大值,时间复杂度为 \(O(n)\) ,要查找 \(n\) 个最大值,因此时间复杂度为 \(O(n^2)\).

  • 在大根堆上寻找最大值的时间复杂度是\(O(1)\),而获取删除最大值之后的向下调整操作时间复杂度为\(O(\log n)\),共寻找 \(n\) 个最大值,因此时间复杂度为 \(O(n\log n)\)

考虑到排序算法的输入是一个乱序的数组,我们首要的任务是将一个普通的数组转换成一个大根堆

方法:从 最后一个节点的父节点 ,逆序遍历数组,依次向下调整。

原理:自底向上,先保证子树满足堆性质,然后逐渐向上扩展直到整棵树都满足堆性质。

综上,堆排序总共分为两个步骤:

  1. 构造大根堆
  2. 选择排序 + 维护堆结构

代码

function heapSort(arr){
  const n = arr.length;
  // 从最后一个节点的父节点开始调整
  // 作用:构造大根堆
  for(let i=Math.floor(n/2)-1; i>=0; i--){
    heapify(arr, i, n);
  } 
  // 将大根堆的根节点和最后一个节点交换,同时维护堆的性质
  // 作用:排序
  for(let i=n-1; i>0; i--){
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
}

// 调整堆
function heapify(arr, index, n){
  let left = 2*index+1;
  let right = 2*index+2;
  while(true){
    let largest = index;
    // 找到左右子树中的最大值
    if(left<n && arr[left]>arr[largest]){
      largest = left;
    }
    if(right<n && arr[right]>arr[largest]){
      largest = right;
    }
    // 如果最大值不是根节点,则交换
    if(largest!==index){
      [arr[index], arr[largest]] = [arr[largest], arr[index]];
      // 更新下一轮的索引
      index = largest;
      left = 2*index+1;
      right = 2*index+2;
    }else{
      break;
    }
  }
}

堆的其它应用

优先队列

优先队列是一种特殊的队列,每个元素都有一个优先级,按优先级顺序出队。刷算法题的时候经常会用到的辅助类PriorityQueue

数组中的第 k 大(或小)元素

可以使用最小堆来高效找到第 \(k\) 大的元素。首先将前 \(k\) 个元素插入堆中,然后遍历数组的其余部分,更新堆,保持堆的大小为 \(k\)。最终堆顶元素就是第 \(k\) 大的元素。

合并多个有序链表

使用最小堆来维护每个有序列表的当前最小元素。每次从堆中取出最小元素,并将该元素所在列表的下一个元素插入堆中。重复该过程直到所有列表都被合并。

事件驱动模拟

Node.js中,多个计时器回调就是使用最小堆记录的,每次事件循环进行到timer阶段,就检查堆顶计时器的剩余时间是否已到达:

  • 如果未到达,则执行下一个阶段的回调任务;
  • 如果已到达,则执行本阶段的所有已到达的定时器回调任务;
    • 每个回调执行完成之后,如果是setInterval,则重新将任务添加到堆中。

热门相关:完美再遇   龙组兵王   九重神格   从现代飞升以后   我的极品美女总裁