Day 29 ： 堆积排序 Heap Sort

今天要来实作最後一个方法，也就是Heap Sort来解Sort an Array。
如果对Heap不熟悉或是已经淡忘的可以回头先温一下Day 24：一起来建构Min-Heap吧。
我们一样会用到Parent和Child之间的关系，不过我们这次会采用Max-Heap的方式来实作！
Max Heap的特徵是第一个节点（node）具有最大值，且我们知道它是一个Unsorted的阵列。

如果要将资料由小到大排序，我们要做以下动作：

1. 把阵列中「第一个节点」和「最後一个节点」位置互换。
2. 假装 heap的最後一个节点（阵列中的最後一个数）被移到我们存放结果的区域。
3. 再持续对第一个节点进行HeapifyDown()。并且把unsorted 的阵列长度-１，存放结果的区域长度+1

举个例子来说，假设我们今天的input阵列为 array = [8, 5, 2, 9, 5, 6, 3]，
我们期望的 output = [2, 3, 5, 5, 6, 8, 9]。

我们可以很明显的发现目前的input array是尚未排序的，
现在假装有一个空阵列[ ]存放结果(result)，开始对input array以inplace的方式制造出Ｍax-heap，结果如下：

max-heap = [9, 8, 6, 5, 5, 2, 3]
result = []

所以现在我们知道最大的数会是9，於是我们直接把Ｍax-heap的头尾做交换swap()

max-heap = [3, 8, 6, 5, 5, 2, 9]
不过我们想像现在的结果是长这样
        => [3, 8, 6, 5, 5, 2][9]
前面的array是我们要继续调整的部分，後面则是放结果的地方
我们再继续把前面调整成 max-heap
max-heap = [8, 5, 6, 3, 5, 2]
重复上面的动作
        => [2, 5, 6, 3, 5][8]
而实际是    [2, 5, 6, 3, 5, 8, 9]

看完上面的动作不知道有没有一点感觉了！
重复以上的方式我们会看到，後面已经排序的部分越来越长，这种排序方式可以达到时间复杂度不管是最糟还是平均都可以是Ｏ(nlogn)，因为我们建构Heap花了Ｏ(n)且加上约执行n回的Ｏ(logn)时间在做remove()的行为。而空间复杂度是Ｏ(1)。

最後来看实作吧！

function heapSort(array) {
  MaxHeapBuild(array);
  for (let endIdx = array.length - 1; endIdx > 0; endIdx--) {
    swap(0, endIdx, array);
    heapifyDown(0, endIdx - 1, array);
  }
  return array;
}

function MaxHeapBuild(array) {
  const firstParentIdx = Math.floor((array.length - 2) / 2);
  for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
    heapifyDown(currentIdx, array.length - 1, array)
  }
}

function heapifyDown(currentIdx, endIdx, heap) {
  let leftChildIdx = currentIdx * 2 + 1;
  while (leftChildIdx <= endIdx) {
    const rightChildIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
    let swapIdx;
    if (rightChildIdx !== -1 && heap[rightChildIdx] > heap[leftChildIdx]) {
      swapIdx = rightChildIdx;
    } else {
      swapIdx = leftChildIdx;
    }
    if (heap[swapIdx] > heap[currentIdx]) {
      swap(currentIdx, swapIdx, heap);
      currentIdx = swapIdx;
      leftChildIdx = currentIdx * 2 + 1;
    } else {
      return;
    }
  }
}

function swap(i, j, heap) {
  const tmp = heap[j];
  heap[j] = heap[i];
  heap[i] = tmp;
}

明天是最後一天了 决定还是有始有终的再玩一题题目好了。

明日题目预告 : Find the closest element in Binary Search Tree