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.

🔗

Listing 6.10.1.

🔗

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());
    }
}

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 1 of 1 activities on this page.

🔗

Prev Top Next