【强化练习】优先级队列经典习题
原创约 17909 字
Prerequisites
Before reading this article, you need to learn:
The main application of a binary heap is a priority queue, which is characterized by dynamic sorting. Elements inserted can automatically maintain the correct order. Of course, a binary search tree can also achieve dynamic sorting, but the priority queue provides a simpler interface and is easier to implement.
Generally, problems that use priority queues can be divided into two categories. One category involves merging multiple sorted sequences into one, and the other involves finding the k-th largest element in multiple sorted sequences. Let's look at each category separately.
Category One: Merging Sorted Sequences
First, let's look at the first category, which includes problems similar to merging sorted linked lists.