基本优先队列

考虑一种队列：每次取出的数据是队列中最小的元素。这种队列可用于程序调度，作业分配等领域，这种队列被称为优先队列，核心的方法有：

  • 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
}