Heap 堆

两种Heap Structure:

1. Max Heap  parent node比 children node大

2. Min Heap 就是parent node比children node小。

Follow up问题：

List all structures that are both heaps and binary search trees. Assume that all elements of the structures have different values.

一个Node的Heap 或者两个Node 的Heap。There are two such structures: a single-node heap/BST and a two-node heap/BST. The latter structure will have a root and a left child. If it had a right child, that element would have to be greater than the root and would thus not satisfy the heap property.

用一个array来模拟出Heap. 东西都装在特定的location。

比如说Node在k position的， 它的parent node 会在K-1/2 position. 他的children node会在 2*k+1 and 2*k+2.

Heap的Run Time 和 Space。Since a heap is a complete binary tree, it has a smallest possible height - a heap with N nodes always has O(log N) height.

添加元素的时候先加到array的最后一位。 然后不断Bubble Up。

删除元素的时候先把root删了，让root的元素先等于整个heap 的rightmost leaf。 然后bubble down

Follow-up:

判断一个东西是不是Max Heap，先check是不是每个node 都小于等于parent。

这里要注意循环的时候K的取值问题。

Below is a max heap