Generalized heaps

Min-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Advertisements

Data structure problems: Heaps and Priority Queues

1. Heap: in-place sorting using heap in O(n log n).

2. Using heaps to improve merge k lists of size n each in O(n log k) time.

3. How to find the kth smallest element using min-heaps in O(k log k) time.

One solution.

– On various priority queue functions: read.