基本优先队列
考虑一种队列:每次取出的数据是队列中最小的元素。这种队列可用于程序调度,作业分配等领域,这种队列被称为优先队列,核心的方法有:
- Insert()方法:将数据插入优先队列
- DeleteMin()方法:将队列中的数据中最小的输出并删除
优先队列可以使用堆这一数据结构实现
二叉堆实现优先队列
二叉堆
二叉堆是除了底层外被完全填满的二叉树,最底层的数据也是从左到右填入(完全二叉树)。因为其填满的特性,可以直接使用数组实现该树型结构:一个位于数组i位置的节点的子节点分别是2*i和2*i+1
优先队列实现
当一个二叉堆实现优先队列时,除了要满足堆的基本特性,还要满足一个特性:对任意一个节点,其值小于其所有的子节点(若有子节点)。则递归的来看,位于根(数组位置0)的节点即为最小的数据。
插入方法
对于堆,每次插入的位置是固定的,若直接将插入元素插入该位置,则优先队列的特性被破坏,因此,需要找到合适的插入位置。操作方法为递归的比较插入位置和插入位置父节点的大小,若满足特性则插入,不满足则交换待插入位置和父节点的数据(将父节点数据写入待插入位置,待插入位置为新的父节点)
删除方法
删除方法有两个功能,第一个功能是将最小的数据弹出,这可以直接返回根节点的值实现;第二个功能是更新新的元素,由于堆少了一个节点,而该节点的位置必须是底层最右侧的节点。因此将该节点数据取出,并插入到跟节点的位置,这样堆的特性被破坏。于是取跟节点为待插入位置,递归的比较待插入节点和子节点的最小节点,获得插入该元素的位置。
代码实现
这段代码写的时候状态比较差,仅供参考
结构体
1 2 3 4 5 6 7 8 9 10
| type nodeData struct { num int data int }
type heap2D struct { heap [17]nodeData lenght int size int }
|
构造函数
1 2 3 4 5 6 7 8 9
| func NewHeap2D() *heap2D { newHeap := &heap2D{} newHeap.size = 15 newHeap.lenght = 1 for i := 0; i < newHeap.size; i++ { newHeap.heap[i] = nodeData{} } return newHeap }
|
插入方法
1 2 3 4 5 6 7 8 9 10 11 12 13
| 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 }
|
弹出方法
1 2 3 4 5 6 7 8 9
| 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 }
|
下移方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| 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 }
|