// 堆元素索引从 1 开始，初始化时先将第一个元素赋值为 0
// 堆有 n 个元素，则它的第一个叶子节点是第 n/2 + 1 个，最后一个非叶子节点是第 n/2 个
// 将 n 个元素逐个插入到一个空堆中，算法复杂度为 O(n log n)
function MaxHeap(arr = []) {
  this.data = [...arr];

  // heapify 方式创建堆结构
  // 利用堆的第 n/2 个元素是最后一个有子节点的元素
  // 从最后一个有子节点的元素开始向上对每个节点进行堆重构
  for (let i = this.parent(arr.length - 1); i >= 0; i--) {
    this.heapifyDown(i);
  }
}

MaxHeap.prototype.size = function() {
  return this.data.length;
};

MaxHeap.prototype.isEmpty = function() {
  return !this.data.length;
};

MaxHeap.prototype.parent = function(index) {
  if (index === 0) {
    throw new Error(`index-0 does't not have parent`);
  }

  return Math.floor((this.data.length - 1) / 2);
};

MaxHeap.prototype.leftChildIndex = function(index) {
  return index * 2 + 1;
};

MaxHeap.prototype.rightChildIndex = function(index) {
  return index * 2 + 2;
};

// 向堆中插入一个元素：插入到最后一个位置，堆插入的元素向上进行堆重构
MaxHeap.prototype.insert = function(value) {
  this.data.push(value);

  // 将最后一个元素进行上浮操作
  this.heapifyUp(this.data.length - 1);
};

MaxHeap.prototype.findMax = function() {
  if (this.size() === 0) {
    throw new Error('Heap is empty');
  }

  // 大顶堆第一个元素就是最大的值
  return this.data[0];
};

// 删除堆中的最大元素：将最后一个元素放到第一的位置，向下进行堆重构
Heap.prototype.extractMax = function() {
  const maxValue = this.findMax();
  // 堆首尾元素交换
  this.swap(0, this.data.length - 1);
  // 删除已经位于堆尾的最大值元素
  this.data.pop();
  // 向下堆重构
  this.heapifyDown(0);

  return maxValue;
};

// 向上堆重构：新元素与父元素比较，新元素大则交换，知道新元素比父元素小为止
Heap.prototype.heapifyUp = function(index) {
  while (index > 0 && this.data[this.parent(index)] < this.data[index]) {
    // 交换数组中位置
    this.swap(index, this.parent(index));
    // 是不是依然不满足堆的性质
    index = this.parent(index);
  }
};

// 向下堆重构：从堆顶开始，比较当前元素和两个子元素，将若当前元素小于子元素中的一个，则将当前元素与较大的子元素交换，知道当前元素大于其子元素
Heap.prototype.heapifyDown = function(index) {
  while (this.leftChildIndex(index) < this.data.length) {
    let leftChildIndex = this.leftChildIndex(index);

    // 极端情况：当左子节点索引小于数组长度时代表绝对没有右子节点，是叶子节点
    if (
      leftChildIndex + 1 < this.data.length &&
      this.data[leftChildIndex + 1] > this.data[leftChildIndex]
    ) {
      leftChildIndex = this.rightChildIndex(index);
    }

    if (this.data[index] > this.data[leftChildIndex]) {
      // 满足堆的性质直接挑出
      break;
    } else {
      // 否则继续交换
      this.swap(index, leftChildIndex);
      index = leftChildIndex;
    }
  }
};

// 堆数组位置交换
Heap.prototype.swap = function(i, j) {
  if (i < 0 || i >= this.data.length || j < 0 || j >= this.data.length) {
    throw new Error('Index is out of range');
  }

  return ([this.data[i], this.data[j]] = [this.data[j], this.data[i]]);
};