1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

package heap

// Heap represents the min heap data structure of []int.
type Heap []int

// Heapify converts nums to a min heap structure in place.
func Heapify(nums []int) *Heap {
	h := Heap(nums)
	for i := len(nums)/2 - 1; i >= 0; i-- {
		siftDown(h, i)
	}
	return &h
}

// Push pushes integer v onto the heap. The complexity is O(logn) where n =
// h.Len().
func (h *Heap) Push(v int) {
	*h = append(*h, v)
	siftUp(*h, len(*h)-1)
}

// Pop removes and return the minimum value from the min heap. The complexity is
// O(logn) where n = h.Len().
func (h *Heap) Pop() int {
	ret := h.Top()
	(*h)[0] = (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	siftDown(*h, 0)
	return ret
}

// Top returns the minimum value from the min heap. The complexity is O(1).
func (h *Heap) Top() int {
	if len(*h) > 0 {
		return (*h)[0]
	}
	return 0
}

// Len returns the length of heap.
func (h *Heap) Len() int {
	return len(*h)
}

func siftDown(h Heap, start int) {
	i, n := start, len(h)
	for {
		leftNode := 2*i + 1
		if leftNode >= n {
			return
		}
		j := leftNode
		if rightNode := leftNode + 1; rightNode < n && h[rightNode] < h[leftNode] {
			j = rightNode
		}
		if h[i] <= h[j] {
			return
		}
		h[i], h[j] = h[j], h[i]
		i = j
	}
}

func siftUp(h Heap, k int) {
	for k > 0 {
		parent := (k - 1) / 2
		if h[parent] > h[k] {
			h[parent], h[k] = h[k], h[parent]
		}
		k = parent
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

import (
	"fmt"
	"./heap"
)

func main() {
	data := []int{1, 3, 5, 7, 9, 2, 4, 6, 8, 10}
	h := heap.Heapify(data)
	fmt.Println(h.Pop())
	fmt.Println(h.Pop())
	fmt.Println(h.Pop())
	h.Push(5)
	h.Push(6)
	h.Push(7)
	fmt.Println(h.Pop())
	fmt.Println(h.Len())
}