Day14：堆积排序(Heap Sort)

堆积(Heap)

堆积，是一种树状结构，用於实现「优先伫列(Priority queue)」。Priority queue是资料结构的一种，可以自由追加数据，读取资料时，从最小值开始选取。
堆积是一种完整的二元树，储存在一维阵列内，分成MaxHeap及MinHeap。

MaxHeap：上一层的节点数值>=下一层的所有节点
MinHeap：上一层的节点数值<=下一层的所有节点

建立Heap步骤如下：

先将一维阵列转换为Heap结构
- 由小到大排序：使用MaxHeap
- 由大到小排序：使用MinHeap
从堆积结构依序取出Root，与最後一的元素交换，再将除了最後一个节点外的一维阵列转换成堆积结构，重复执行直到剩下最後一个元素，排序完成。

堆积排序(Heap Sort)

堆积排序最初要将n个数储存到堆积中的时间是O(n log(n))。
此外，每回合取出最大值，再重新排列堆积，所需时间是O(log n)，回合数是n，堆积重整後接着排序的执行时间也是O(n log(n))，由此得知，堆积排序的整体执行时间是O(n log(n))。
与气泡排序、选择排序、插入结构相比，堆积排序处理速度较快，但也因为这种复杂的资料结构，建置与维护变得复杂。

import random

#从1-100中随机读取8个数字
nums = random.sample(range(1,100), 9)
print(nums)

def max_heapify(h, n, x):
    #如果(2*x+1) <= n，表示有右子节点
    if (2*x+1) <= n :
        #如果h[2*x] > h[2*x+1]，表示左子节点大於右子节点
        if h[2*x] > h[2*x+1]:
            max = 2*x
        else:
            max = 2*x+1
    else:
        max = 2*x
    #如果h[x]<h[max]，则两个子节点互换
    if h[x] < h[max]:
        h[x], h[max] = h[max], h[x]
        #如果2*max<=n，表示h[max]也有子节点，recursion max_heapify是否与孙节点互换
        if 2*max <= n:
            max_heapify(h, n, max)

#将任何阵列转换为Max Heap
def build_max_heap(h, n):
    #回圈变数
    for i in range(n//2, 0, -1):
        max_heapify(h, n, i)

def heap_sort(h, n):
    build_max_heap(h, len(h)-1)
    print(h)
    for i in range(n, 1, -1):
        h[i], h[1] = h[1], h[i]
        if i > 2:
            max_heapify(h, i-1, 1)
        print(h)

heap_sort(nums, len(nums)-1)
print(nums)

let heapSize;
let arr = [15, 3, 17, 18, 20, 2, 1, 666];
heapSort();
console.log(arr);

function buildMaxHeap() {
  heapSize = arr.length - 1;
  for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
    maxHeapify(i);
  }
}

function maxHeapify(i) {
  let largest;
  let l = i * 2 + 1;
  let r = i * 2 + 2;
  if (l <= heapSize && arr[l] > arr[i]) {
    largest = l;
  } else {
    largest = i;
  }

  if (r <= heapSize && arr[r] > arr[largest]) {
    largest = r;
  }

  if (largest != i) {
    // swap A[i] with A[largest]
    let temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    maxHeapify(largest);
  }
}

function heapSort() {
  buildMaxHeap();
  for (let i = arr.length - 1; i >= 0; i--) {
    // exchange A[0] with A[i]
    let temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapSize -= 1;
    maxHeapify(0);
  }

  return arr;
}