如何添加和恢复堆？

Question

在一个问题中，我们应该从这个 maxHeap 中删除四 (4) 个元素（见下图），并且每次删除一个元素时，堆属性都必须恢复。包含剩余堆元素的列表必须按级别顺序排列。

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

这段代码给了我这个答案，根据我的测验，这是正确的：

_ 45 35 40 20 25 15 30 10

我的问题是在添加到堆时遇到以下挑战：通过将以下七个元素按照它们在上面的堆中列出的顺序添加来构建一个 minHeap。每增加一个元素，堆属性需要恢复

要添加到堆中的数字：

30 75 35 15 70 20 10

完成后，按级别顺序列出元素。包含前导下划线以指示未使用索引 0 上的元素。

免责声明：如前所述，这是一个测验，因此您不会完成我的作业。我只是好奇。也许我应该使用 PriorityQueue...我一直在尝试，但我没有取得任何进展。

Answer 1

正如您已经实施的那样，删除工作如下：

删除最后一个节点并将其值放入根节点
筛选向下根的值直到堆属性被恢复（在heapify中实现）

反方向插入：

在末尾追加新值的节点
筛选向上那个值直到堆属性被恢复。

如何添加和恢复堆？

How to add and restore a heap?

java

oop

algorithm

heap

data-structures