堆 & 优先队列 & 多路归并

库heapq 创建堆及基本操作优先队列的实现经典题目

堆的原理部分参加

🎈

堆，本页介绍 heapq 库和经典题目

库heapq

堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

创建堆及基本操作

heapq有两种方式创建堆，：

一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中

另外一种就是使用heap.heapify(list)转换列表list成为堆结构


# 第一种方法
h = []
heapq.heappush(h, val) # 入堆
heapq.heappop(h)       # 出堆
h[0]  # 如果只是想获取最小值而不是弹出，使用 h[0]

# 第二种方法
nums = [2, 3, 5, 1, 54, 23, 132]
heapq.heapify(nums)

heapq.heappush(nums, val)  # 入堆
heapq.heappop(nums) # 出堆

如果需要获取堆中最大或最小的范围值，则可以使用heapq.nlargest() 或heapq.nsmallest() 函数


"""
函数定义：
heapq.nlargest(n, iterable[, key])
    - Return a list with the n largest elements from the dataset defined by iterable. 
    - key if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key=str.lower
    - Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
"""
import heapq

nums = [1, 3, 4, 5, 2]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

输出：
[5, 4, 3]
[1, 2, 3]

优先队列的实现

一般用堆来实现优先队列


queue = []
heapq.heappush(queue, item)  # 入队
heapq.heappop(queue) # 出队

但如果存入优先队列的对象本身不可比大小，可以将（idx, item）入队列，idx为全局变量每次入队之后 idx += 1，这样 idx 就可以作为优先级，且整个入堆的对象也可以比较大小

使用堆封装一个优先队列


class PriorityQueue:
	def __init__(self)
			self._queue = []
			self._idx = 0
	
    def push(self, item):
        heapq.heappush(self._queue, (self._idx, item))
        # 参数 1：队列
        # 参数 2：将整个元组添加到队列中，目的是为了方便比较大小
        self._idx += 1

    def pop(self):
        heapq.heappop(self._queue)[-1]