基本优先队列
考虑一种队列：每次取出的数据是队列中最小的元素。这种队列可用于程序调度，作业分配等领域，这种队列被称为优先队列，核心的方法有：
- Insert()方法：将数据插入优先队列
- DeleteMin()方法：将队列中的数据中最小的输出并删除
优先队列可以使用堆这一数据结构实现
二叉堆实现优先队列
二叉堆
二叉堆是除了底层外被完全填满的二叉树，最底层的数据也是从左到右填入（完全二叉树）。因为其填满的特性，可以直接使用数组实现该树型结构：一个位于数组i位置的节点的子节点分别是2*i和2*i+1
优先队列实现
当一个二叉堆实现优先队列时，除了要满足堆的基本特性，还要满足一个特性：对任意一个节点，其值小于其所有的子节点（若有子节点）。则递归的来看，位于根（数组位置0）的节点即为最小的数据。
插入方法
对于堆，每次插入的位置是固定的，若直接将插入元素插入该位置，则优先队列的特性被破坏，因此，需要找到合适的插入位置。操作方法为递归的比较插入位置和插入位置父节点的大小，若满足特性则插入，不满足则交换待插入位置和父节点的数据（将父节点数据写入待插入位置，待插入位置为新的父节点）
2d_heap_insert
删除方法
删除方法有两个功能，第一个功能是将最小的数据弹出，这可以直接返回根节点的值实现；第二个功能是更新新的元素，由于堆少了一个节点，而该节点的位置必须是底层最右侧的节点。因此将该节点数据取出，并插入到跟节点的位置，这样堆的特性被破坏。于是取跟节点为待插入位置，递归的比较待插入节点和子节点的最小节点，获得插入该元素的位置。
2d_heap_delete
代码实现
这段代码写的时候状态比较差，仅供参考
结构体
type nodeData struct {
num int
data int
}
type heap2D struct {
heap [17]nodeData
lenght int
size int
}
构造函数
func NewHeap2D() *heap2D {
newHeap := &heap2D{}
newHeap.size = 15
newHeap.lenght = 1
for i := 0; i < newHeap.size; i++ {
newHeap.heap[i] = nodeData{}
}
return newHeap
}
插入方法
func (h *heap2D) Insert(din nodeData) error {
if h.lenght > h.size {
return errors.New("heap full")
}
i := 0
for i = h.lenght; h.heap[i/2].num >= din.num && i != 0; i = i / 2 {
h.heap[i] = h.heap[i/2]
// 若插入标记小于父节点标记，则向父节点移动
}
h.heap[i] = din //插入
h.lenght++
return nil
}
弹出方法
func (h *heap2D) DeleteMin() (nodeData, error) {
if h.lenght == 0 {
return nodeData{}, errors.New("heap empty")
}
dout := h.heap[1] //取出根节点数据，该数据为优先级最高的节点
err := h.DownFlow(1, h.heap[h.lenght-1]) //调用下移方法将堆中的最后一个节点从根节点插入
h.lenght--
return dout, err
}
下移方法
func (h *heap2D) DownFlow(nodeNum int, insert nodeData) error {
if nodeNum >= h.lenght {
return errors.New("errors")
} else if 2*nodeNum >= h.lenght {
// 无子节点，直接插入
h.heap[nodeNum] = insert
return nil
} else if insert.num < h.heap[h.findMinSon(nodeNum)].num {
// 两个子节点均大于待插入数据，直接插入
h.heap[nodeNum] = insert
return nil
}
// 两个子节点的最小标号小于带插入数据标号，递归该过程
next := h.findMinSon(nodeNum)
h.heap[nodeNum] = h.heap[next]
return h.DownFlow(next, insert)
}
// 该方法用于计算出最小子节点标号
func (h *heap2D) findMinSon(nodeNum int) int {
if 2*nodeNum+1 >= h.lenght {
return 2 * nodeNum
}
if h.heap[2*nodeNum].num > h.heap[2*nodeNum+1].num {
return 2*nodeNum + 1
}
return 2 * nodeNum
}
