DS Binary Heap Operations

Section 6.10 Binary Heap Operations

The basic operations we will implement for our binary heap are as follows:

BinaryHeap() creates a new empty binary heap.
insert(k) adds a new item to the heap.
getMin() returns the item with the minimum key value, leaving the item in the heap.
delete() returns the item with the minimum key value, removing the item from the heap.
isEmpty() returns True if the heap is empty, False otherwise.
size() returns the number of items in the heap.
heapify(list) builds a new heap from a list of keys.

Listing 6.10.1 demonstrates the use of some of the binary heap methods.

public class BinaryHeapTest {
    public static void main(String[] args) {
        BinaryHeap<Integer> myHeap = new BinaryHeap<>();
        myHeap.insert(5);
        myHeap.insert(7);
        myHeap.insert(3);
        myHeap.insert(11);
        System.out.println("Min value: " + myHeap.getMin());

        System.out.println("Deleting items: ");
        System.out.println(myHeap.delete());
        System.out.println(myHeap.delete());
        System.out.println(myHeap.delete());
        System.out.println(myHeap.delete());
    }
}

Listing 6.10.1.

Here is its output:

Min value: 3
Size: 4
Deleting items:
3
5
7
11

Notice that no matter what order we add items to the heap, the smallest is removed each time.

You have attempted of activities on this page.

Prev Top Next