24 ms·

I wonder if this is just a naming thing... the terms "min-heap" (or max-heap) and "priority queue", while not identical, are often used interchangeably. So if y

• troebr 14y ago
  From my point of view, the min-heap is appropriate to pop/peek the min value (O(1)), but how do you 'peek' the first 5 values for instance? This is a valid min-heap: (5 ((7 (9, 10)), (8 (11, 12)))). Where in (a (b, c)) b and c are children of a. If you want to peek(5) you have to: 1. peek 5 2. peek the min of 7 and 8 (7) 3. now you have to peek the min of 9, 10 and 8. 4. it's 8, now you have to peek the min of 9,10,11 and 12 The thing is, the only guarantee you have is that a root node of a tree or subtree is smaller than its children. You know nothing of a sibling subtree. I think maintaining a simple list is the simplest way of doing that, and to speed up lookups for existing items, an index (map item->index) can be maintained. Or the other way around, keep the objects in a map and the keys in the order list. Considering a size n=5 it might even be reasonable to do everything with a simple array and iterate over it.