: jank    :   : 4995    : 2018-03-06 00:43  数据结构和算法

package main

import (
	"fmt"
)

var heap = []int{1, 33, 23, 3, 425, 24, 11, 333, 98, 93, 2}

func Less(a, b int) bool {
	return heap[a] < heap[b]
}

func Len() int {
	return len(heap)
}

func Swap(a, b int) {
	heap[a], heap[b] = heap[b], heap[a]
}

//下沉
//	i 父节点
//	j1 左儿子
//	j2 右二字
func Down(i, n int) {
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 {
			break
		}

		j2 := j1 + 1
		j := j1
		if j2 < n && Less(j2, j) {
			j = j2
		}

		if Less(i, j) { //如果子节点大于父节点则交换，否则终止此次循环
			break
		}
		Swap(i, j)
		i = j
	}
}

//创建堆
func MakeHeap() {
	n := Len()
	for i := n/2 - 1; i >= 0; i-- {
		Down(i, n)
	}
}

//堆排序
func HeapSort() {
	n := Len()
	for i := n - 1; i > 0; i-- {
		Swap(0, i) //将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
		Down(0, i) //重新调整结构，使其满足堆定义
	}
}

//上浮
func Up(j int) {
	for {
		i := (j - 1) / 2          //获取当前节点的父节点
		if i == j || Less(i, j) { //判断当前父节点如果大于子节点则退出循环
			break
		}
		Swap(i, j)
		j = i
	}
	return
}

//添加数据
func Push(a int) {
	heap = append(heap, a)
	Up(Len() - 1)
	return
}

//弹出根节点
func Pop() int {
	n := Len() - 1
	Swap(0, n) //交换当前顶点和最后一个数的位置
	Down(0, n) //从根节点的左右儿子开始重新对树进行向下排位
	old := heap
	n = len(old)
	x := old[n-1]
	heap = old[0 : n-1]
	return x
}

//删除节点
func Remove(a int) bool {
	n := Len() - 1
	if a < 0 || a > n {
		return false
	}
	Swap(a, n)
	heap = heap[0:n]
	Down(a, n)
	return true
}

func main() {
	MakeHeap() //首先创建堆，
	//	HeapSort() //进行堆排序
	fmt.Println(heap)
	//Push(50)
	//	Push(3)
	//	Push(55)
	//	MakeHeap()
	HeapSort()
	//	fmt.Println(heap)

	fmt.Println("添加数字50后:", heap)
}