Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The FindMin member function locates the item with the smallest key
in a given priority queue
and the DequeueMin member function removes it from the queue.
Since the smallest item in a heap is found at the root,
the FindMin operation is easy to implement.
Program 
shows how it can be done.
Clearly, the running time of the FindMin operation is O(1).
Program: LeftistHeap Class FindMin Member Function Definitions
Since the smallest item in a heap is at the root,
the DequeueMin operation must delete the root node.
Since a leftist heap is a binary heap,
the root has at most two children.
In general when the root is deleted,
we are left with two non-empty leftist heaps.
Since we already have an efficient way to merge leftist heaps,
the solution is to simply merge the two children of the root
to obtain a single heap again!
Program shows how the DequeueMin operation
of the LeftistHeap class can be implemented.
Program: LeftistHeap Class DequeueMin Member Function Definition
The running time of Program is determined
by the time required to merge the two children of the root (line 13)
since the rest of the work in DequeueMin can be done in constant time.
Consider the running time to delete the root of a leftist heap T
with n internal nodes.
The running time to merge the left and right subtrees of T
where 
and 
are the null path lengths of the left and right
subtrees T, respectively.
In the worst case, 
and 
.
If we assume that 
,
the running time for DequeueMin is 
.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.