c++ - 如何实现最大堆

Question

我有构建最大堆的代码，但它一直返回我给它的同一个数组。我确定这是一个小错误，但我似乎无法弄清楚。感谢您的帮助。

可编译示例代码:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i; }
    int getRight(int i) { return (2 * i) + 1; }
    int getParent(int i) { return i / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int maxHeap[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[]);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int maxHeap[]) {
    int heap_size = size;
    int n = size;
    int temp;

    Build_Max_Heap(maxHeap, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        temp = maxHeap[0];
        maxHeap[0] = maxHeap[i];
        maxHeap[i] = temp;

        heap_size = heap_size - 1;
        Max_Heapify(maxHeap, 0, heap_size);
    }

    for (int i = 0; i < 8; i++) {
        std::cout << maxHeap[i] << std::endl;
    }
}

void Heaparr::Build_Max_Heap(int maxHeap[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(maxHeap, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l <= heap_size) && (heapArray[l] > heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r <= heap_size) && (heapArray[r] > heapArray[largest])) {
        largest = r;
    }

    int temp;
    if (largest != i) {
        temp = heapArray[i];
        heapArray[i] = heapArray[largest];
        heapArray[largest] = temp;

        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};
    Heaparr t;
    t.heapSort(hArray);
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
}

Answer 1

我对代码做了一些修正(我尽量不对原始代码做太多改动):

• getLeft、getRight 和 getParent 公式是错误的(例如:当 i == 0 子级必须是 1 和 2 并且您的代码是 0 和 1。返回类型是也错了，应该是int(数组索引)。
• 除了 int[] 和 insert 中的 member variable 之外，您是否在所有方法中都收到了 double[]，如果您需要全部改回 double
，则全部更改为 int[]
• 使用 std::swap 作为数组中的交换值。
• 将数组的长度添加到heapSort(在方法中此信息丢失，需要通过参数传递)。

注意事项:

• 我没看到你在哪里使用成员变量 maxHeap ，因为除了 getMax 和 insert 之外的所有方法都使用参数传递的数组而不是成员变量(也许你应该在构造函数或 heapSort 方法中初始化。
• 尝试使用 std::vector 而不是 C Array

代码:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i + 1; }
    int getRight(int i) { return 2 * i + 2; }
    int getParent(int i) { return (i - 1) / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int heapArray[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[], int heap_size);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int heapArray[], int heap_size) {
    size = heap_size;
    int n = size;
    Build_Max_Heap(heapArray, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        std::swap(heapArray[0], heapArray[i]);
        heap_size = heap_size - 1;
        Max_Heapify(heapArray, 0, heap_size);
    }
}

void Heaparr::Build_Max_Heap(int heapArray[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(heapArray, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l < heap_size) && (heapArray[l] < heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r < heap_size) && (heapArray[r] < heapArray[largest])) {
        largest = r;
    }

    if (largest != i) {
        std::swap(heapArray[i], heapArray[largest]);
        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};

    Heaparr t;
    t.heapSort(hArray, sizeof(hArray)/sizeof(hArray[0]));
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
    return 0;
}

输出: 99, 32, 15, 12, 8, 5, 4, 1,

使用 C++11 在 GCC 4.9.0 中测试