已發布·持續改進
樹與堆積 指南 · 6/6
本章目前僅提供英文版。
You will meet trees and heaps far more often as ready-made components than as code you write yourself. This chapter shows where they appear in real systems and which pitfalls catch people when using the standard libraries.
std::map and std::set (red-black trees in the major implementations) and Java TreeMap and TreeSet (red-black trees) keep keys ordered and answer nearest-value queries such as floorKey or lower_bound in O(log n).heapq is a set of functions that treat a plain list as a min-heap. The usual way to get a max-heap is to push negated values (Python 3.14 also adds max-heap functions such as heappush_max). When two priorities tie, tuple comparison moves on to the next element, and an incomparable object such as a dict raises TypeError. Putting an increasing counter in the middle fixes this and also keeps equal priorities in insertion order.
import heapq
import itertools
queue, counter = [], itertools.count()
def add(priority, task):
heapq.heappush(queue, (priority, next(counter), task))
add(2, {"name": "backup"})
add(1, {"name": "deploy"})
add(2, {"name": "report"}) # equal priority, yet dicts are never compared
while queue:
p, _, task = heapq.heappop(queue)
print(p, task["name"]) # 1 deploy, 2 backup, 2 report
scores = [5, 1, 9, 3]
max_heap = [-s for s in scores] # flip the sign to use it as a max-heap
heapq.heapify(max_heap)
print(-max_heap[0], heapq.nlargest(2, scores)) # 9 [9, 5]A heap does not support changing the priority of, or removing, an arbitrary element. The standard workaround is lazy deletion: push a new entry, mark the old one as stale, and skip stale entries when they are popped. The familiar line if d > dist[u]: continue in Dijkstra's algorithm is exactly this technique.
std::priority_queue is a max-heap by default. Pass std::greater as the third template argument for a min-heap. top() and pop() are separate calls, and calling either on an empty queue is undefined behaviour, so check empty() first.
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
int main() {
std::priority_queue<int> maxq; // max-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minq; // min-heap
for (int x : {5, 1, 9, 3}) { maxq.push(x); minq.push(x); }
std::cout << maxq.top() << ' ' << minq.top() << '\n'; // 9 1
using Item = std::pair<int, std::string>; // (distance, name) uses pair ordering
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
pq.push({7, "b"});
pq.push({3, "a"});
std::cout << pq.top().second << '\n'; // a
}PriorityQueue is a min-heap by default; a Comparator changes the order. A comparator written as subtraction, (a, b) -> a - b, overflows for large values, so use Integer.compare or Comparator.comparingInt. Iterating with for or printing with toString() shows the internal array order, not sorted order; to see items in order, take them out with poll().
import java.util.Comparator;
import java.util.PriorityQueue;
public class Tasks {
record Task(String name, int priority) {}
public static void main(String[] args) {
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
max.addAll(java.util.List.of(5, 1, 9, 3));
System.out.println(max.peek()); // 9
PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
pq.add(new Task("backup", 2));
pq.add(new Task("deploy", 1));
while (!pq.isEmpty()) System.out.println(pq.poll().name()); // deploy, backup
}
}Trees form the backbone of file systems, database indexes, sorted maps and schedulers, while heaps are the basic tool for timers, graph algorithms and top-K computations. When using a standard library, keep in mind its default order (min-heap in Python and Java, max-heap in C++), how ties are handled, and lazy deletion for priority changes, and you will avoid most pitfalls.
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。