我正在尝试通过两种方法insert和extract_max来实现Max-heap。但是extract_max当前无法正常工作，因为它没有提取堆中的最大整数，我认为这是因为heapify。我已经尝试调试了几个小时，但无法弄清楚哪里出了问题。任何输入将不胜感激。
class Heap {
int heap_array[];
int n_elems = 0;
int capacity;
// Constructor
Heap(int _capacity) {
capacity = _capacity;
heap_array = new int[capacity];
}
/**
* Private method for maintaining the heap.
* @param i, index of the element to heapify from
**/
private void heapify(int i) {
int left = 2*i + 1;
int right = 2*i+ 2;
int largest = i;
//if left ≤ heap_length[A] and A[left] > A[largest] then:
if (left <= n_elems && heap_array[left] > heap_array[largest]) {
largest = left;
//System.out.println("largest = left");
}
//if right ≤ heap_length[A] and A[right] > A[largest] then:
if (right <= n_elems && heap_array[right] > heap_array[largest]) {
//System.out.println("largest = right");
largest = right;
}
//if largest ≠ i then:
if (largest != i) {
int swap = heap_array[i];
heap_array[i] = heap_array[largest];
heap_array[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(largest);
}
}
/**
* Add an element to the heap and ensure the heap property
* Throws an exception if trying to add elements to a full heap.
* @param x Element to add
*/
public void insert(int x) throws Exception {
if(is_full()) {
throw new Exception("The heap is full");
} else {
// Insert the element at end of Heap
heap_array[n_elems++] = x;
//n_elems++;
// Heapify from root
heapify(0);
}
}
public int extract_max() throws Exception {
//Get the largest
// Get the last element
int root = heap_array[0];
int lastElement = heap_array[n_elems];
// Replace root with first element
heap_array[0] = lastElement;
// Decrease size of heap by 1
n_elems--;
// heapify the root node
heapify(0);
// return new size of Heap
return root;
}
public int capacity() {
return capacity;
}
public int size() {
return n_elems;
}
public boolean is_empty() {
return n_elems == 0;
}
public boolean is_full() {
return n_elems == capacity;
}
public void print() {
for(int i = 0; i < n_elems; i++) {
System.out.println(heap_array[i]);
}
}
/**
* Remove and return largest element, and maintain the heap property.
* Throws an exception if trying to extract an element from an empty heap.
*/
/**
* For convenience, a small program to test the code.
* There are better ways of doing this kind of testing!
* @throws Exception
*
*/
static public void main(String args[]) throws Exception { // A simple test program
// Declare two heaps. Both should work nicely!
Heap h1 = new Heap(100);
Heap h2 = new Heap(10);
int data[] = {1, 4, 10, 14, 7, 9, 3, 8, 16};
//
// Insert 1 element to heap 1, and several to heap 2.
//
h2.insert(9);
h2.insert(10);
h2.insert(8);
h2.insert(11);
h2.insert(12);
h2.insert(15);
System.out.println("Size " + h2.size());
h2.print();
System.out.println("Max " + h2.extract_max());
}
}
第一个问题是您的insert不正确。仅添加到最后并调用heapify(0)并不会带来任何好处。 heapify将检查根元素及其两个子元素，确定根是最大的项目，然后退出，什么也不做。因此，您只是将内容依次添加到列表中。
要插入最大堆，请执行以下操作：
所以insert应该看起来像这样：
public void insert(int x) throws Exception {
if(is_full()) {
throw new Exception("The heap is full");
}
// Insert the element at end of Heap
heap_array[n_elems++] = x;
// now sift it up
int current = nelems-1;
int parent = (current-1)/2;
while (current > 0 && heap_array[current] > heap_array[parent]) {
int swap = heap_array[parent];
heap_array[parent] = heap_array[current];
heap_array[current] = swap;
current = parent;
parent = (current-1)/2;
}
}
我认为您在extract_max中也有问题。您有：
int lastElement = heap_array[n_elems];
但是最后一个元素实际上位于索引n_elems-1]。我认为您想要：
int lastElement = heap_array[n_elems-1];
这很有意义，因为如果为n_elems == 1，那么堆中的唯一项将是heap_array[0]处的根；