A tree-based data structure that orders each parent relative to its children so that an extremal value is available at the root. In a max-heap, every parent is at least as large as its children. Heap implementations provide one way to realize a priority queue; the abstract queue and its implementing structure are distinct concepts.
A heap data structure supporting a meld operation that combines two heaps into one while preserving the heap order. The cost of melding distinguishes implementations such as a leftist heap from ordinary binary heaps.
A meldable heap satisfying the min-heap ordering: each parent key is no greater than its children's keys. It combines efficient merging with access to the current minimum key.
A binary meldable heap satisfying heap order and the leftist condition: at each node, the shortest path to a missing child is no longer in the right subtree than in the left. Melding recurses down right spines, swaps children when needed, and takes logarithmic time.
A heap data structure in which every parent key is at least as large as its children's keys. The root therefore stores a largest key, allowing a priority queue to retrieve a current maximum efficiently.
Articles by others on the same topic
There are currently no matching articles.