Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The Enqueue member function of the LeftistHeap class
is used to put items into the heap.
Enqueue is easily implemented using the Merge operation.
I.e., 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 
.
Program: LeftistHeap Class Enqueue Member Function Definition
The expression for the running time for the Insert operation follows directly from that of the Merge operation. I.e., 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.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.