大根堆数据结构

// 大根堆性质：
// 1.完全二叉树
// 2.父节点不小于子节点
// 3.使用数组表示大根堆时，父节点i的左右子节点下标分别2i+1, 2i+2
// 4.完全二叉树的特性：下标最大的非叶子节点的下标为数组长度n/2-1  (关键点)

// 大根堆步骤：
// 1.大根堆创建
// 2.大根堆插入
// 3.大根堆删除
// 包含调整函数，遍历所有非叶子节点调整，插入为大根堆插入尾部进行调整，删除为将需要删除的节点替换到尾部，然后对删除节点进行调整

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// 调整函数，只能调整某个节点及其子节点符合大根堆性质
int adjustHeap(int a[], int i, int n) {
    int left = 2*i + 1;
    int right = 2*i + 2;
    int max = i;

    if (a == nullptr || i < 0 || n <= 0 || i > n) {
        return -1;
    }

    if (left < n && a[left] > a[i]) {
        max = left;
    }

    if (right < n && a[right] > a[i]) {
        max = right;
    }

    if (max != i) {
        swap(a[i], a[max]);
        adjustHeap(a, max, n);
    }

    return 0;
}

// 创建大根堆
int creatHeap(int a[], int n) {
    if (a == nullptr || n < 0) {
        return -1;
    }

    for (int i = (n >> 1) - 1; i >= 0; i++) {
        adjustHeap(a, i, n);
    }

    return 0;
}

// 插入函数，将其插入完全二叉树的尾部，然后做调整，假设这里a已经预分配的n+1个空间
int insertHeap(int a[], int n, int value) {
    if (a == nullptr || n < 0) {
        return -1;
    }

    a[n] = value;
    n = n + 1;
    adjustHeap(a, (n-1) >> 1, n);

    return 0;
}

// 删除函数，这里只写出删除最大节点，然后再做调整
// 也可进化到删除任意节点，只需要将删除掉的节点值与最后一个节点交换数据后再调整即可
int deleteHeap(int a[], int n) {
    if (a == nullptr || n < 0) {
        return -1;
    }

    a[0] = a[n-1];
    adjustHeap(a, 0, n-1);

    return 0;
}