Putting Items into a Leftist Heap

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Putting Items into a Leftist Heap

The Enqueue method of the LeftistHeap class is used to put items into the heap. Enqueue is easily implemented using the Merge operation. That is, to enqueue an item in a given heap, we simply create a new heap containing the one item to be enqueued and merge it with the given heap. The algorithm to do this is shown in Program .

program25911
Program: LeftistHeap class Enqueue method.

The expression for the running time for the Insert operation follows directly from that of the Merge operation. That is, the time required for the Insert operation in the worst case is

where d is the null path length of the heap into which the item is inserted. If we assume that two keys can be compared in constant time, the running time for Insert becomes simply , where n is the number of nodes in the tree into which the item is inserted.