堆和优先队列

1.堆

    1.1 定义       

              堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

                        堆中某个节点的值总是不大于或不小于其父节点的值；

                        堆总是一棵完全二叉树。

                        

                    

     

    1.2 用数组实现二叉堆

         

 

package arr

//用slice实现堆
type Heap struct {
	H []interface{}
}

/**
 * parent 返回节点的父亲节点索引
 * @index int
 */
func (h *Heap) Parent(index int) int {
	if h.H[index] == 0 {
		return 0
	}
	return (index - 1) / 2
}

/**
 * leftchild 返回节点的左孩子节点索引
 * @index int
 */
func (h *Heap) Leftchild(index int) int {
	return 2*index + 1
}

/**
 * rightchild 返回节点的右孩子节点索引
 *@index int
 */
func (h *Heap) Rightchild(index int) int {
	return 2*index + 2
}

   

1.3 堆中的CURD

     1.3.1 添加元素 Sift Up

                

 

/**
 * add 向堆中添加节点
 * @E 泛型
 */
func (h *Heap) Add(E int) []int {
	h.H = append(h.H, E)
	return siftup(h, len(h.H)-1)
}

//siftup函数 判断新加入的元素是否满足堆的性质
func siftup(h *Heap, k int) []int {
	for k > 0 && h.H[k] > h.H[h.Parent(k)] {
		//互换位置
		swap(h, k, h.Parent(k))
		k = h.Parent(k)
	}
	return h.H
}

//swap两个元素位置互换
func swap(h *Heap, i, j int) {
	z := h.H[i]
	h.H[i] = h.H[j] //子节点换成父节点
	h.H[j] = z      //父节点换成子节点
}

 

    1.3.2 取出元素 Sift Down

                            

        取出最大元素

/**
 * findmax 删除并输出最大的元素
 */
func (h *Heap) Findmax() int {
	rel := h.H[0]
	//首位互换
	swap(h, 0, len(h.H)-1)
	//删除末尾
	h.H = h.H[0 : len(h.H)-1]
	//下沉操作
	siftdown(h, 0)
	return rel
}

//siftdown 0节点删除后,最后一个节点上升为0节点的下沉操作
func siftdown(h *Heap, k int) {
	for h.Leftchild(k) < len(h.H) { 		//确定左孩子不超过范围
		//j为左右两个孩子中较大的那个的索引
		j := h.Leftchild(k)
		if j+1 < len(h.H) && h.H[j] < h.H[j+1] { //右孩子存在且右孩子比左孩子大,则j为右孩子
			j = h.Rightchild(k)
		}
		if h.H[k] > h.H[j] {
			break
		}
		swap(h, k, j)
		k = j
	}
}

 

    1.3.3 取出最大元素,并替换一个新元素 replace

                               

/**
 * replace 取出最大元素,并用e来代替
 */
func (h *Heap) Replace(E int) int {
	rel := h.H[0]
	h.H[0] = E
	siftdown(h, 0)
	return rel
}

         

    1.3.4 将任意的数组整理成堆 heapify

                               

/**
 * heapify 传递一个slice 封装成heap
 */
func (h *Heap) Makeheap() []int {
	for a := h.Parent(len(h.H) - 1); a >= 0; a-- {
		siftdown(h, a)
	}
	return h.H
}

 

    1.4 全部代码

package arr

//用slice实现堆
type Heap struct {
	H []int
}

/**
 * add 向堆中添加节点
 * @E 泛型
 */
func (h *Heap) Add(E int) []int {
	h.H = append(h.H, E)
	return siftup(h, len(h.H)-1)
}

//siftup函数 判断新加入的元素是否满足堆的性质
func siftup(h *Heap, k int) []int {
	for k > 0 && h.H[k] > h.H[h.Parent(k)] {
		//互换位置
		swap(h, k, h.Parent(k))
		k = h.Parent(k)
	}
	return h.H
}

//swap两个元素位置互换
func swap(h *Heap, i, j int) {
	z := h.H[i]
	h.H[i] = h.H[j] //子节点换成父节点
	h.H[j] = z      //父节点换成子节点
}

/**
 * findmax 删除并输出最大的元素
 */
func (h *Heap) Findmax() int {
	rel := h.H[0]
	//首位互换
	swap(h, 0, len(h.H)-1)
	//删除末尾
	h.H = h.H[0 : len(h.H)-1]
	//下沉操作
	siftdown(h, 0)
	return rel
}

//siftdown 0节点删除后,最后一个节点上升为0节点的下沉操作
func siftdown(h *Heap, k int) {
	for h.Leftchild(k) < len(h.H) { //确定左孩子不超过范围
		//j为左右两个孩子中较大的那个的索引
		j := h.Leftchild(k)
		if j+1 < len(h.H) && h.H[j] < h.H[j+1] { //右孩子存在且右孩子比左孩子大,则j为右孩子
			j = h.Rightchild(k)
		}
		if h.H[k] > h.H[j] {
			break
		}
		swap(h, k, j)
		k = j
	}
}

/**
 * replace 取出最大元素,并用e来代替
 */
func (h *Heap) Replace(E int) int {
	rel := h.H[0]
	h.H[0] = E
	siftdown(h, 0)
	return rel
}

/**
 * heapify 传递一个slice 封装成heap
 */
func (h *Heap) Makeheap() []int {
	for a := h.Parent(len(h.H) - 1); a >= 0; a-- {
		siftdown(h, a)
	}
	return h.H
}

/**
 * parent 返回节点的父亲节点索引
 * @index int
 */
func (h *Heap) Parent(index int) int {
	if h.H[index] == 0 {
		return 0
	}
	return (index - 1) / 2
}

/**
 * leftchild 返回节点的左孩子节点索引
 * @index int
 */
func (h *Heap) Leftchild(index int) int {
	return 2*index + 1
}

/**
 * rightchild 返回节点的右孩子节点索引
 *@index int
 */
func (h *Heap) Rightchild(index int) int {
	return 2*index + 2
}

 

2.优先队列

    2.1 定义

                普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有*先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

                   

 

    2.2 基层的实现对比

                             

 

    2.3 代码实现 (基于之前的堆)

package arr

type Priority struct {
	Heap Heap
}

/**
 * Getfront 查看队首元素
 */
func (p *Priority) Getfront() int {
	return p.Heap.H[0]
}

/**
 * enqueue 入队操作
 */
func (p *Priority) Enqueue(E int) {
	p.Heap.Add(E)
}

/**
 * dequeue 出队操作	
 */
func (p *Priority) Dequeue(E int) {
	p.Heap.Findmax()
}