在一個問題中，我們應該從這個 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 上的元素。
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.
uj5u.com熱心網友回復：
正如您已經實施的那樣，洗掉的作業方式如下：
- 洗掉最后一個節點并將其值放在根節點中
- 過篩向下直到恢復堆屬性根的值（在實施
heapify）
插入作業在另一個方向：
- 在節點末尾附加新值
- 篩起來，直到恢復堆性質該值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/325971.html