c++ - 如何在C++中使用数组来堆化minheap？

该程序应该可以正常运行，但是不能！假设您正在通过将nmubers插入数组来构建最小堆。每次插入后都应带有Heapify函数，以确保数字类型不违反minheap规则。这是我写的，但是有问题，我做不到！

int P(int i) //returning the index of parent
{

    if (i % 2 == 0) { i = ((i - 2) / 2); }
    else { i = ((i - 1) / 2); }
    return i;
}

void Heapify(double A[], int i)//putting the smallest value in the root because we have a min heap
{
    if (P(i) != NULL && A[i] < A[P(i)])
    {
        temp = A[P(i)];
        A[P(i)] = A[i];
        A[i] = temp;
        Heapify(A, P(i));
    }
}

最佳答案

一般来说，您的heapify函数似乎并没有考虑到左分支和右分支的最小值。让我向您展示一个理想的，可行的实现（面向对象，因此您可能希望将堆作为参数传递）。您可以在整个互联网上找到确切的伪代码，因此我并没有真正提出任何独特的东西。

void Heap::Heapify (int i)
{
    int l = left(i);
    int r = right(i);
    int lowest;

    if (l < heap_size && heap[l] -> value < heap[i] -> value )
        lowest = l;
    else
        lowest = i;
    if (r < heap_size && heap[r] -> value < heap[lowest] -> value)
        lowest = r;
    if (lowest != i)
    {
        swap (heap[i], heap[lowest]);
        Heapify(lowest);
    }
}

哪里

int left    ( int i ) { return 2 * i; }
int right   ( int i ) { return 2 * i + 1; }

如您所见，算法首先检查左子项和右子项中哪个值较低。该值将与当前值交换。那就是一切。

关于c++ - 如何在C++中使用数组来堆化minheap？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22411642/