Day 24：一起来建构Min-Heap吧

在实作之前我们先来认识Heap

堆积 (Heap)，是一种特殊的完全(complete)二元树，也就是除了最後一层树叶，每一层都是长满的。

而今天要建构的Min-Heap多了一个特点，就是了父结点都要小於或等於子结点; 相反的，Max-Heap则是父结点都要大於或等於子结点。

我将要用一个没有被排列过的阵列，采用in-place的方式，来建构出一个符合min-Heap性质的阵列，我们会实作两个函式，分别是heapifyDown() 和 heapifyUp()，它们都可以用来建构Min-Heap（build Heap），此外我们还需要其他两个函式分别是insert()以及remove()。

实作两个函式前我们要先知道如何推得heap的父结点t以及子结点的索引（index）以及它们之间的关系式。我们先以下图为例

我可以观察出，假设现在在的节点 index = i

则 leftChild = 2i+1 ; rightChild = 2i+2，而 parent = (i-1) / 2 取 floor

利用这种简单的计算方式，我们就可以很轻易地取得parent和child（以O(1)的时间复杂度）

接下来我们就来看如何在heap中插入节点→ insert()

假设我们今天要把上方的heap加入0，我们该如何操作？

1. 我们会把0加在最後面(last node)，也就是3的rightChild，但我们知道加进去的元素不可能一定洽在正确的位置，所以我们需要将它作向上调整的动作（ heapifyUp() ），这个方法会不断的将插入的节点与其父节点比较，若有需要则会swap()

2. 以这张图来说：因为 3 > 0 所以需要交换，以次类推如下图，最後可以获得最右边的min heap
   

3. 若用阵列的几角度来看 ，则是利用push的方式加到阵列最後面 array = [ 1, 2, 3, 6, 4, 5, 0]，0的index为6，要比较的parent就是 floor((6-1)/2) = 2 （array[2] = 3），我们直接在array做swap的动作。以下先来写swap()

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

1. 依照上面重复的逻辑就是heapifyUp()

不过在这里暂停一下，先来写remove()，这里的remove我们要做的是：移除heap的最小值（以後一定会碰到我们用heap的资料结构来移除最大或最小值 → peek() 其实就是回传array[0] ）

操作方式如下：

1. 我们直接把array的array[0]和array的最後一个元素（array[array.length-1]）做swap，然後直接用pop()的方式移除阵列最後一个元素，而後再对heap做调整（heapifyDown()：其实就是拿array[0]开始往後调整的感觉），换作是图就会如下。
   

2. 注意heapifyDown是要把左右儿子小的往上面交换

3. 若用阵列的几角度来看 ，则是先swap() → array = [ 3, 2, 1, 6, 4, 5, 0 ] → pop() → array = [ 3, 2, 1, 6, 4, 5] → heapifyDown()

建构 Heap 使用heapifyDown，从最左边的parent开始（较佳）-> 整体时间复杂度: O(N)
空间复杂度 : O(1) 不需额外的空间

说到这里我们就直接来实作吧！

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  buildHeap(array) {
		// 采用heapifyDown, Time: O(n), space O(1)
		const firstIdx = Math.floor((array.length -2) / 2);
		for(let currentIdx = firstIdx; currentIdx >= 0; currentIdx --){
			this.heapifyDown(currentIdx, array.length, array);
		}
    return array;
  }

  heapifyDown(currentIdx, endIdx, heap) {
    let leftChildIdx = currentIdx*2+1;
		while(leftChildIdx<=endIdx){
			// 确认是否有右儿子
			const rightChildIdx = currentIdx*2 +2 <= endIdx ? currentIdx*2 +2 : -1;
			let swapIdx;
			// 找出较小的child
			if(rightChildIdx!==-1 && heap[rightChildIdx] < heap[leftChildIdx]){
				swapIdx = rightChildIdx;
			}else{
				swapIdx = leftChildIdx;
			}
			// 如果较小的child 小於 parent 则swap，且要继续往"下"确认
			if(heap[swapIdx] < heap[currentIdx]){
				this.swap(currentIdx, swapIdx, heap);
				currentIdx =  swapIdx;
				leftChildIdx = currentIdx*2+1;
			}else{
				return;
			}
		}
  }

   heapifyUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx -1)/2);
		// 每次比较当下node和parent的值，如果比较小要和parent swap ，而後再继续往"上"检查
		while(currentIdx > 0 && heap[currentIdx] < heap[parentIdx]){
			this.swap(currentIdx, parentIdx, heap);
			currentIdx = parentIdx;
			parentIdx =  Math.floor((currentIdx -1)/2);
		}
  }

	// 传回root O(1)
  peek() {
    return this.heap[0];
  }

 //把根移除 
	remove() {
		//把跟和最後一个元素交换後 再做heapifyDown调整
  	this.swap(0, this.heap.length -1, this.heap);
		const removeValue = this.heap.pop();
		this.heapifyDown(0, this.heap.length -1, this.heap);
		return removeValue;
  }


  insert(value) {
		// 加到最array後面
    this.heap.push(value);
		// 用heapifyUp 调整
		this.heapifyUp(this.heap.length - 1, this.heap);
  }
	
	swap(i, j, heap){
		const tmp = heap[j];
		heap[j] = heap[i];
		heap[i] = tmp;
	}
}

其实max-heap就是仿造上面的程序码把一些大於小於做调整就可以了！别忘了自己coding一下喔！

明日题目预告：我们已经陆续用了不少的sort来解问题，明天开始就让我们实作不同的经典排序方法来解同一道题目吧！之後也会用到heap的结构来解喔！ Sort an Array