1.数据结构之堆排序

堆是一种数据结构，本文实现的二叉堆，而堆先决条件是一颗完全二叉树，由完全二叉树性质来说，可以使用数组array存放；数组array第一个位置不放元素，从1开始，对后面下标i来说，后面下标对应的父节点为当前下标除以2后结果向下取整，左子节点为当前对下标2，右子节点为下标2+1，可以方便找到任意节点对父子节点，在调整堆时候很方便；同时堆的实现方式很适合实现优先队列。
LeetCode中 215. 数组中的第K个最大元素这个问题就可以用堆的方式来解决，本文接下来主要是如何用javascript实现堆结构。

2.基础组成

使用数组存储堆的数据，下标从1开始计算，然后根据传入的优先级比较函数确认构建的堆结构是大顶堆还是小顶堆，默认是小顶堆，比较结果是true和false；堆结构是一颗完全二叉树，所以可以方便的找到当前节点的父节点和左右子树节点，第一节中已经介绍过了。

// 构造函数，能够接受自定义的优先级比较方法
 constructor(compare) {
   this.array = [0]; // 初始化存堆数据堆数组，下标从1开始
   this.compare = (typeof compare === 'function') ? compare : this._defaultCompare; //接受传入优先级比较函数，没有传用默认的
 }

  //默认比较函数，a是否比b更解决堆顶，默认小顶堆
 _defaultCompare(a, b) {
   return a < b; // 大顶堆为a>b
 }

 //获取左右还有父节点
 _left(i) {
   return i * 2;
 }
 _right(i) {
   return i * 2 + 1;
 }
 _parent(i) {
   return Math.floor(i / 2);
 }

3.新元素入堆后调整

将新的元素添加到整个堆的末尾，同时让新加入的元素进行“上浮”，直到符合堆定义的位置；具体操作是不断将该元素和父节点比较优先级，如果新的优先级更高，应该更接近堆顶，就和父元素交换位置，直到满足条件；

push(item) {
  let {array} = this;
  array.push(item);
  this._up(array.length - 1); //上浮元素
}

//上浮第i个元素，param i
_up(i) {
  let {array, compare, _parent} = this;
  //i=1到堆顶，否则有机会继续上浮
  //_parent(i)获取父节点下标，满足上浮条件的话（不在堆顶而且比较函数返回的是true
  while (i > 1 && compare(array[i], array[_parent(i)])) { 
    this._swap(_parent(i), i); // 交换父节点和当前节点
    i = _parent(i);
  }
}

4.元素出堆后调整

出堆的顺序-先和末尾元素调换位置（为了堆顶出堆后调整）然后末尾元素也就是堆顶出堆；接下来对现在的堆顶（之前的末尾元素）进行下沉调整堆结构，使之满足堆的要求；
下沉的话，如果当前元素的左子树存在就有下沉的可能性，然后如果当前的右子树也存在就比较左右子树，然后如果比较函数返回true，小顶堆的话也就是右子树小于左子树的话，让右子树赋值给左子树值（也就是小顶堆左子树存左右子树中最小值），然后比较左子树和当前节点的值，如果当前节点值小于左子树直接返回结束，否则的话就继续下沉节点（交换当前节点和左子树的值，然后让当前节点为左子树，继续下沉比较）。

// 返回元素，出队
  pop() {
    if (this.size === 0) { // 当前无元素就返回null
      return null
    }
    let {array} = this;
    this._swap(1, array.length - 1); //换末尾上来，堆顶放到最后
    let res = array.pop();
    this._down(1);//换上来的元素尝试下沉；
    return res;
  }

  //下沉第i个元素 params i
  _down(i) {
    let {array, compare, _left, _right, size} = this;
    //如果i是堆底，就沉不下去了
    while (_left(i) <= size) { //size队列长度
      let left_i = _left(i);
      //选孩子节点中更靠近堆顶的，这样能保持原本的左右顺序
      if (_right(i) <= size && compare(array[_right(i)], array[left_i])) { 
        left_i = _right(i);
      }
      //如果当前i比子节点更靠近堆顶，就不用下沉了
      if (compare(array[i], array[left_i])) {
        return;
      }
      //继续下沉
      this._swap(i, left_i);
      i = left_i;
    }
  }

5.完整代码

class Heap {

  // 构造函数，能够接受自定义的优先级比较方法
  constructor(compare) {
    this.array = [0]; // 初始化存堆数据堆数组，下标从1开始
    this.compare = (typeof compare === 'function') ? compare : this._defaultCompare; //接受传入优先级比较函数，没有传用默认的
  }

  // 入队 新的元素添加到整个堆的末尾，让新加入的元素进行“上浮”，到符合堆定义的位置；具体操作是不断将该元素和父节点比较优先级，
  //如果新的优先级更高，应该更接近堆顶，就和父元素交换位置，直到满足条件；
  push(item) {
    let {array} = this;
    array.push(item);
    this._up(array.length - 1); //上浮元素
  }

  //上浮第i个元素，param i
  _up(i) {
    let {array, compare, _parent} = this;
    //i=1到堆顶，否则有机会继续上浮
    while (i > 1 && compare(array[i], array[_parent(i)])) { //_parent(i)获取父节点下标
      this._swap(_parent(i), i);
      i = _parent(i);
    }
  }

// 返回元素，出队
  pop() {
    if (this.size === 0) { // 当前无元素就返回null
      return null
    }
    let {array} = this;
    this._swap(1, array.length - 1); //换末尾上来，堆顶放到最后
    let res = array.pop();
    this._down(1);//换上来的元素尝试下沉；
    return res;
  }

  //下沉第i个元素 params i
  _down(i) {
    let {array, compare, _left, _right, size} = this;
    //如果i是堆底，就沉不下去了
    while (_left(i) <= size) {
      let left_i = _left(i);
       //选孩子节点中更靠近堆顶的，这样能保持原本的左右顺序
      if (_right(i) <= size && compare(array[_right(i)], array[left_i])) {
        left_i = _right(i);
      }
      //如果当前i比子节点更靠近堆顶，就不用下沉了
      if (compare(array[i], array[left_i])) {
        return;
      }
      //继续下沉
      this._swap(i, left_i);
      i = left_i;
    }
  }

  // 返回优先级最高元素，不出队
  peek() {
    return this.array[1];
  }

// 队列长度
  get size() {
    return this.array.length - 1;
  }

  //获取左右还有父节点
  _left(i) {
    return i * 2;
  }

  _right(i) {
    return i * 2 + 1;
  }

  _parent(i) {
    return Math.floor(i / 2);
  }

  //交换
  _swap(i, j) {
    [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
  }

  //默认比较函数，a是否比b更解决堆顶，默认小顶堆
  _defaultCompare(a, b) {
    return a < b; // 大顶堆为a>b
  }

  //根据data数据生成堆
  static heapify(data, compare = undefined) {
    let heap = new Heap(compare);
    for (let i of data) {
      heap.push(i)
    }
    return heap;
  }
}

let heap = Heap.heapify([1, 2, 3]);
heap.push(8)
heap.pop();
heap.pop();
heap.pop();
heap.size();
heap.peek();

PS：本文实现思路主要源自于这里，但是本文实现相比之下略显繁琐，LeetCode的这个题解更简洁的实现了堆的构建