Priority queue

Explain the heap contract

A priority queue exposes the highest- or lowest-priority item efficiently. A binary min-heap stored in an array maintains that every parent is no greater than its children. Insert appends then bubbles up; extract-min swaps in the last element then bubbles down; peek reads the root. These operations are O(log n), peek is O(1), and heapifying n initial items is O(n).

Ask whether priorities change, whether stable ordering among equal priorities matters, and whether a min or max queue is needed. For lazy deletion, push updated entries and discard stale ones when popped; for true decrease-key, choose a structure or indexed heap that supports it. Test empty extraction, duplicate priorities, custom comparators, and integer overflow in priority calculations. A priority queue is not automatically sorted: iterating its internal array does not yield priority order. Use it for repeatedly selecting the current best candidate, such as Dijkstra, k-way merge, or scheduling, only after the actual application is clear.