package myheap

import (
    "testing"
    . "github.com/smartystreets/goconvey/convey"
)

func TestInit(t *testing.T) {
    Convey("test", t, func() {
		nodes := []Node{
			Node{3},
            Node{6},
            Node{9},
            Node{1},
            Node{2},
            Node{5},
            Node{8},
            Node{4},
            Node{7},
		}

		Convey("Test Init()", func(){
			So(Init(nodes), ShouldResemble, []Node{
				Node{1},
                Node{2},
                Node{5},
                Node{4},
                Node{3},
                Node{9},
                Node{8},
                Node{6},
                Node{7},
			})
        })

        nodes = Init(nodes)

        Convey("Test Push()", func(){
			So(Push(Node{0}, nodes), ShouldResemble, []Node{
				Node{0},
                Node{1},
                Node{5},
                Node{4},
                Node{2},
                Node{9},
                Node{8},
                Node{6},
                Node{7},
                Node{3},
			})
        })

        nodes = Push(Node{0}, nodes)

        Convey("Test Pop()", func(){
			So(Pop(nodes), ShouldResemble, []Node{
				Node{1},
				Node{2},
				Node{5},
				Node{4},
				Node{3},
				Node{9},
				Node{8},
				Node{6},
                Node{7},
			})
		})
	})
}

package myheap

import "fmt"

type Node struct {
	Value int
}

// 用于构建结构体切片为最小堆，需要调用down函数
func Init(nodes []Node)  []Node{
	for i := len(nodes)/2 - 1; i >= 0; i-- {
		down(nodes, i, len(nodes))
	}
	return nodes
}

// 需要down（下沉）的元素在切片中的索引为i，n为heap的长度，将该元素下沉到该元素对应的子树合适的位置，从而满足该子树为最小堆的要求
func down(nodes []Node, i, n int) {
	var parent int = i
	var child int = i*2+1
	var tmp int = nodes[i].Value
	for child < n {
		//取较小的孩子
		if (child < n-1) && (nodes[child].Value > nodes[child+1].Value) {
			child++
		}
		if tmp > nodes[child].Value {
			nodes[parent].Value = nodes[child].Value
			parent = child
			child = parent*2 + 1
		} else {
			break
		}
	}
	nodes[parent].Value = tmp
}

// 用于保证插入新元素(j为元素的索引,切片末尾插入，堆底插入)的结构体切片之后仍然是一个最小堆
func up(nodes []Node, j int) {
	var child int = j
	var parent int = (j-1)/2
	var tmp int = nodes[j].Value
	for parent >= 0 && child >= 1 {
		if tmp < nodes[parent].Value {
			nodes[child].Value = nodes[parent].Value
			child = parent
			parent = (child-1)/2
		} else {
			break
		}
	}
	nodes[child].Value = tmp
}

// 弹出最小元素，并保证弹出后的结构体切片仍然是一个最小堆，第一个返回值是弹出的节点的信息，第二个参数是Pop操作后得到的新的结构体切片
func Pop(nodes []Node)  []Node {
	//min := nodes[0]
    nodes[0].Value = nodes[len(nodes)-1].Value
    nodes = nodes[ :len(nodes)-1]
    down(nodes,0,len(nodes)-1)
    return nodes
}

// 保证插入新元素时，结构体切片仍然是一个最小堆，需要调用up函数
func Push(node Node, nodes []Node) []Node {
	nodes = append(nodes, node)
    up(nodes, len(nodes)-1)
    return nodes
}

// 移除切片中指定索引的元素，保证移除后结构体切片仍然是一个最小堆
func Remove(nodes []Node, node Node) []Node {
	for i := 0; i < len(nodes); i++ {
        if node.Value == nodes[i].Value {
            nodes[i].Value = nodes[len(nodes)-1].Value
            nodes = nodes[:len(nodes)-1]
            down(nodes, i, len(nodes)-1)
        }
    }
    return nodes
}

//用于打印堆
func PrintList(nodes []Node) {
    for _, ele := range nodes {
        fmt.Printf("%d ", ele.Value)
    }
    fmt.Printf("\n")
}