In a problem, we were supposed to remove four (4) elements from this maxHeap (see image below), and every time an element was removed, the heap property had to be restored. The list with the remaining heap elements had to be in level-order.

public class HeapSort {

public static void heapify(int node[], int n, int i) {
    int largest = i,        // Initialize largest as root
        l = 2 * i   1,      // Left = 2*i   1
        r = 2 * i   2;      // Right = 2*i   2

    if (l < n && node[l] > node[largest]) {
        largest = l;                                // If left child is larger than root (n = size of heap)
    }
    if (r < n && node[r] > node[largest]) {
        largest = r;                                // If right child is larger than largest
    }
    if (largest != i) {
        int swap = node[i];
        node[i] = node[largest];                    // If largest is not root
        node[largest] = swap;
        heapify(node, n, largest);                  // Recursively heapify the affected sub-tree
    }
}

/**
 * Deletes the root from the Heap.
 */
public static int deleteRoot(int node[], int n) {
    int lastElement = node[n - 1];      // Get the last element
    node[0] = lastElement;              // Replace root with first element
    n -= 1;                             // Decrease size of heap by 1
    heapify(node, n, 0);                // Heapify the root node
    return n;                           // Return new size of Heap
}

/**
 * A utility function to print array of size N 
 */
public static void printArray(int array[], int n) {
    System.out.print("_ ");
    for (int i = 0; i < n;   i) {
        System.out.print(array[i]   " ");
    }
}

public static void main(String args[]) {
    // Insert values representing the Heap.
    int node[] = {65, 55, 60, 45, 25, 40, 50, 10, 35, 15, 20, 30};
    int n = node.length,
        removes = 4;        // Insert the number of elements you want to delete (e.g.: 4).
    
    for(int i = 0; i < removes; i  ) {
        n = deleteRoot(node, n);
    }
    printArray(node, n);
}}

This code gave me this answer, which is correct according to my quiz:

_ 45 35 40 20 25 15 30 10

My problem is when adding to the heap, with the following challenge: Build a minHeap by adding the following seven elements in the order in which they are listed to the heap above. Every time an element is added, the heap property needs to be restored.

Numbers to be added to the heap:

30 75 35 15 70 20 10

When you are done, list the elements in level-order. Include a leading underscore to indicate that the element on index 0 is not used.

Disclaimer: this, as mention, WAS a quiz and therefore you wouldn't be doing my assignment. I am just curious. Maybe I should use PriorityQueue... I've been trying, but I am not getting anywhere.

CodePudding user response：

As you have already implemented, a deletion works as follows:

• Delete the last node and put its value in the root node
• Sift down the root's value until the heap property is restored (implemented in heapify)

Insertion works in the other direction:

• Append the node with the new value at the end
• Sift up that value until the heap property is restored.