Heap Datastructure
The heap datastructure is a clever design that makes an array behave like a binary tree, and the root of the tree will always be the min or max value.
For any index i in the heap:
- its left child will be at
2*i - its right child will be at
2*i + 1 - its children will always be greater or lesser than the current node.
Example
package misspos
type heap struct {
data []int
index int
}
func NewHeap(n int) *heap {
return &heap{
data: make([]int, n),
}
}
func (h *heap) Empty() bool {
return h.index < 1
}
func (h *heap) Add(x int) {
h.data[h.index] = x
h.climb(h.index)
h.index++
}
func (h *heap) Peek() int {
return h.data[0]
}
func (h *heap) Pop() int {
v := h.data[0]
h.data[0] = 0
h.lift()
h.index--
return v
}
func (h *heap) climb(i int) {
p := (i - 1) / 2
for i > 0 && h.data[p] > h.data[i] {
h.data[p], h.data[i] = h.data[i], h.data[p]
i = p
p = (i - 1) / 2
}
}
func (h *heap) lift() {
for i := 0; i < len(h.data); {
j := 2*i + 1
if j >= h.index {
if i < h.index-1 {
h.data[i], h.data[h.index-1] = h.data[h.index-1], h.data[i]
h.climb(i)
}
break
}
if j+1 < h.index && h.data[j] > h.data[j+1] {
j++
}
h.data[i], h.data[j] = h.data[j], h.data[i]
i = j
}
}
func FirstMissing(x []int) int {
h := NewHeap(len(x))
missing := 1
for _, v := range x {
if v < missing {
continue
}
if v > missing {
h.Add(v)
continue
}
missing += 1
for !h.Empty() && missing >= h.Peek() {
missing = h.Pop() + 1
}
}
return missing
}
type heap struct {
data []int
index int
}
func NewHeap(n int) *heap {
return &heap{
data: make([]int, n),
}
}
func (h *heap) Empty() bool {
return h.index < 1
}
func (h *heap) Add(x int) {
h.data[h.index] = x
h.climb(h.index)
h.index++
}
func (h *heap) Peek() int {
return h.data[0]
}
func (h *heap) Pop() int {
v := h.data[0]
h.data[0] = 0
h.lift()
h.index--
return v
}
func (h *heap) climb(i int) {
p := (i - 1) / 2
for i > 0 && h.data[p] > h.data[i] {
h.data[p], h.data[i] = h.data[i], h.data[p]
i = p
p = (i - 1) / 2
}
}
func (h *heap) lift() {
for i := 0; i < len(h.data); {
j := 2*i + 1
if j >= h.index {
if i < h.index-1 {
h.data[i], h.data[h.index-1] = h.data[h.index-1], h.data[i]
h.climb(i)
}
break
}
if j+1 < h.index && h.data[j] > h.data[j+1] {
j++
}
h.data[i], h.data[j] = h.data[j], h.data[i]
i = j
}
}
func FirstMissing(x []int) int {
h := NewHeap(len(x))
missing := 1
for _, v := range x {
if v < missing {
continue
}
if v > missing {
h.Add(v)
continue
}
missing += 1
for !h.Empty() && missing >= h.Peek() {
missing = h.Pop() + 1
}
}
return missing
}