// 從下到上堆化
func (h *Heap) downToUpHeapify(pos int) {
    for pos / 2 > 0 && h.data[pos/2].Less(h.data[pos]) { // 如果存在父節(jié)點(diǎn) & 值大于父節(jié)點(diǎn)
        h.swap(pos, pos/2) // 交換兩個(gè)值的位置
        pos = pos /2 // 將操作節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的位置
    }
}

// 從上到下堆化
func (h *Heap) upToDownHeapify() {
    max := h.len
    i := 1
    pos := i
    for {
        if i * 2 <= max && h.data[i].Less(h.data[i*2]) { // 如果有左子樹，且自己小于左子樹
            pos = i*2 
        }
        if i *2 +1 <= max && h.data[pos].Less(h.data[i*2+1]) { // 如果有右子樹，且自己小于右子樹
            pos = i*2+1
        }
        if pos == i { // 如果位置沒有變化，說明堆化結(jié)束
            break
        }
        h.swap(i, pos) // 交換當(dāng)前位置和下一個(gè)位置的內(nèi)容
        i = pos // 操作下一個(gè)位置
    }
}

type Interface interface {
    sort.Interface
  Push(x interface{}) // 把元素添加到 Len() 的位置
    Pop() interface{}   // 刪除并返回 Len() - 1 的元素.
}
// sort.Interface
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

func Push(h Interface, x interface{}) {
    h.Push(x) // 向數(shù)據(jù)集添加一個(gè)元素
    up(h, h.Len()-1) // 從下向上堆化
}
// 從下向上堆化的內(nèi)容
func up(h Interface, j int) {
  // h 表示堆，j 代表需要堆化的元素 index
    for {
        i := (j - 1) / 2 // 定義 j 的父 index
        if i == j || !h.Less(j, i) { // 如果兩個(gè)元素相等 或者 父元素小于當(dāng)前元素
            break  // 堆化完成
        }
        h.Swap(i, j) // 交換父元素和當(dāng)前元素
        j = i // index 變?yōu)楦冈氐?index
    }
}

// 返回堆頂?shù)脑兀h掉它
func Pop(h Interface) interface{} {
  n := h.Len() - 1 // 獲取最終堆長度（去掉最后一個(gè)元素）
    h.Swap(0, n)     // 交換堆頂和最后一個(gè)元素
    down(h, 0, n)    // 從上到下堆化
    return h.Pop()   // 彈出最后一個(gè)元素
}
func down(h Interface, i0, n int) bool {
    i := i0 // 堆頂 index
    for {
        j1 := 2*i + 1  // 左孩子 index
        if j1 >= n || j1 < 0 { // j1 大于堆長度 或 溢出
            break  // 堆化結(jié)束
        }
        j := j1 // j = 左孩子
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { 
      // j2 = 右孩子；j 小于堆長度 && 右孩子小于左孩子
            j = j2 // j = 2*i + 2 = 右孩子 
        }
    // 上面是從左右孩子選出小的那個(gè)，將 index 賦值給 j
        if !h.Less(j, i) { // 如果 堆頂小于 j , 堆化結(jié)束
            break
        }
        h.Swap(i, j) // 交換堆頂元素和 j
        i = j // 切換到下一個(gè)操作 index
    }
  // 返回 元素是否有移動(dòng)
  // 此處是一個(gè)特殊設(shè)計(jì)，用來判斷向下堆化是否真的有操作
  // 當(dāng)刪除中間的元素時(shí)，如果向下堆化沒有操作的話，就需要再做向上堆化
    return i > i0 
}

func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1 // 堆的長度
    if n != i { // 如果不是堆頂
        h.Swap(i, n) // 交換刪除元素 和 最后一個(gè)元素
        if !down(h, i, n) { // 從上到下堆化
            up(h, i) // 如果沒有成功，就從下島上堆化
        }
    }
    return h.Pop() // 彈出最后一個(gè)元素
}
func Fix(h Interface, i int) {
  // i 是值被改變的 index
    if !down(h, i, h.Len()) {   // 從上到下堆化
        up(h, i) // 如果沒有成功，就從下島上堆化
    }
}

func Init(h Interface) {
    n := h.Len()  // n 是堆長度
  // i = 最后一個(gè)非葉子節(jié)點(diǎn)的 index； i >= 堆頂； index 自減
    for i := n/2 - 1; i >= 0; i-- {
    // 從當(dāng)前節(jié)點(diǎn)開始，從上到下堆化
        down(h, i, n)
    }
}