c++ - 在特定情况下无法向下渗透 MIN 二进制堆

Question

我正在尝试在我的源 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.
}

删除最小值:

void BinaryHeap::deleteMin() {


    if(size>=1)
    {
        heap[1]=heap[size-1];
        size--;
        percolateDown(1);
    }
}

获取分钟:

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


}

向下渗透:

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 情况，以便向下渗透结合左右子索引以从提到的情况中传递，但我并没有真正弄清楚如何。也许绘制形成的树是个好主意。

Answer 1

为了提高可读性，我更改了一点插入方法。首先，如果有足够的空间，我们将一个新元素插入到数组的末尾。然后我们检查堆属性是否有效，换句话说，如果后者更大，我们继续进行根交换子和父。

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 这两个函数中，您在索引方面遇到了问题，因为目前您的算法意味着零索引。我已将 size - 1 更改为 size。

void deleteMin() {
    if(size >= 1) {
        heap[1] = heap[size];
        size--;
        percolateDown(1);
    }
}

同样，您需要在 percolateDown 函数中使用 less 或 equal 运算符来进行索引比较。此外，您是从 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);
    }
}