我正在尝试在源cpp文件中实现最小类型的二进制堆，并使用一些不同输入和操作的特定情况对其进行测试。但是，我的断言测试未通过以下操作序列：
cout << "Testing percolate down If there are two children nodes that are both smaller than
the parent... " << endl;
heap.insert(23);
heap.insert(43);
heap.insert(234);
heap.insert(321);
heap.insert(243);
cout<<"nerde"<<endl;
cout << "Testing percolate down If there are two children nodes that are both smaller than
the parent..." << endl;
assert(heap.getMin() == 23);
heap.deleteMin();
assert(heap.getMin() == 43);
heap.deleteMin();
assert(heap.getMin() == 234);
heap.deleteMin();
cout<<"nerde78"<<endl;
assert(heap.getMin() == 243);
heap.deleteMin();
assert(heap.getMin() == 321);
heap.deleteMin();
我的输出在上述
cout<<"nerde78"<<endl;处给出断言失败我基于堆数组的实现从索引1开始（不使用零索引）。而且我认为所有DeleteMin，GetMin和Insert函数都是正确的。
堆的构造函数：
BinaryHeap::BinaryHeap(int capacity) {
this->capacity = capacity;
// The element at index 0 is not used!
// The root element will be placed at index 1
heap = new int[capacity+1];
size = 0;
}
插入：
void BinaryHeap::insert(int element) {
//Parcolate up
if(size<capacity)
{
int hole=++size;
for( ;hole>1 && element<heap[hole/2];hole/=2 )
{
heap[hole]=heap[hole/2];
}
heap[hole]=element;
}
// TO BE COMPLETED
// The capacity of the heap is assumed to be fixed.
// Insert the element if size < capacity
// Do nothing otherwise.
// After the new element is inserted, perform a percolate up operation here.
// You can add a percolateUp method to the class,
// or just implement the operations within this insert method.
}
DeleteMin：
void BinaryHeap::deleteMin() {
if(size>=1)
{
heap[1]=heap[size-1];
size--;
percolateDown(1);
}
}
GetMin：
int BinaryHeap::getMin() {
if(size<1)
{
return -1;
}
else
return heap[1];
// TO BE COMPLETED
// If the size is less than 1, return -1
// Otherwise, return the value of the root node
}
percolateDown：
void BinaryHeap::percolateDown(int hole) {
// TO BE COMPLETED
// Compare the node with its children; if they are in the correct order, stop
// Otherwise, swap the element with the smallest child
// Repeat the operation for the swapped child node
int min_index = hole;
int left = hole * 2 ;
int right = hole * 2 + 1;
if (left < size && heap[left]<heap[min_index]) {
min_index = left;
}
if (right < size && heap[right]<heap[min_index]) {
min_index = right;
}
if (min_index != hole) {
swap(hole, min_index);
percolateDown( hole);
}
}
交换：
void BinaryHeap::swap(int i, int j) {
int t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
我当前的错误信息：
Assertion failed: heap.getMin() == 243
我猜想我需要包括另一个if / else案例，以便向下结合左右孩子索引从下面提到的案例中获得渗透，但是我并没有真正弄清楚如何。也许绘制形成的树是一个好主意。
最佳答案
我更改了一些插入方法以提高可读性。首先，如果有足够的空间，我们将新元素插入数组的末尾。然后，我们检查一下heap属性是否有效，换句话说，我们进行到根交换子节点和父交换节点（如果后者更大）。
void insert(int element) {
if(size < capacity) {
int hole = ++size;
heap[hole] = element;
while(hole > 1 && heap[hole] < heap[hole / 2]){
swap(hole / 2, hole);
hole /= 2;
}
}
}
然后，在deleteMin和percolateDown这两个函数中，索引编制都存在问题，因为当前您的算法暗含零索引编制。我已将尺寸更改为1。
void deleteMin() {
if(size >= 1) {
heap[1] = heap[size];
size--;
percolateDown(1);
}
}
同样，在percolateDown函数中需要较少或相等的运算符来进行索引比较。另外，您要从min_index而不是作为父级的hole继续进行下去。
void percolateDown(int hole) {
int min_index = hole;
int left = hole * 2;
int right = hole * 2 + 1;
if (left <= size && heap[left] < heap[min_index]) {
min_index = left;
}
if (right <= size && heap[right] < heap[min_index]) {
min_index = right;
}
if (min_index != hole) {
swap(hole, min_index);
percolateDown(min_index);
}
}