数据结构-堆、shiftUP、shiftDown、heapify

堆排序

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

shiftUP

用于创建堆，不知道有多少数据；
以父子数大小来排序；
第一个为数组1 这样父子树的下标为k/2;

//堆第一个为数组1  这样父子树的下标为k/2;
void MaxHeap::shiftUp(int k) {
//    while (k > 1) {
//        int parent = (k)/2;
//        if (data[k] > data[parent]) {
//            std::swap(data[k], data[parent]);
//            k = parent;
//        }else {
//            break;
//        }
//    }
    
//优化写法
    while (k > 1 && data[k] > data[k/2]) {
        std::swap(data[k], data[k/2]);
        k = k/2;
    }
}

shiftDown

• 用于移除最大值后，仍然是个堆
• 用于已知数据，排成一个堆
  以左右子数与父子数比较来排序

1、 递归写法

//当shifup 把最大值和最后一个交换时，然后移除最大值，然后shifdown 重新排序
void MaxHeap::shiftDown(int k) {
    //递归
    int l = 2 * k;
    int r = 2 * k + 1;
    int max = k;
    if (l <= count && data[max] < data[l]) {
        max = l;
    }
    if (r <= count && data[max] < data[r]) {
        max = r;
    }
    if (max != k) {
        std::swap(data[max], data[k]);
        shiftDown(max);
    }
}

2、非递归

void MaxHeap::shiftDown(int k) {
    //非递归
    while (2 * k + 1 <= count) {
        int l = k * 2;
        if (l + 1 <= count && data[l] < data[l + 1]) {
            l++;
        }
        if(data[k] > data[l]){
            return;
        }else {
            std::swap(data[k], data[l]);
            k = l;
        }
    }
}

Heapify

对于一组已知数据，只要对

下面是i为0时的例子
Heapify :将堆的末端子节点作调整，使得子节点永远小于父节点。

I 为目标借点下标
parent :为I节点父节点
c1为左子节点
c2为右子节点

parent = (I - 1)/2;

c1 = 2* I + 1;
c2 = 2*I + 2;

image.png

C 实现代码

void heapify(int *arr, int n, int i) {
    if (i >= n) {
        return;
    }
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int maxPartent = i;
    if (c1 < n && arr[c1] > arr[maxPartent]) {
        maxPartent = c1;
    }
    if (c2 < n && arr[c2] > arr[maxPartent]) {
        maxPartent = c2;
    }
    
    if (maxPartent != i) {
        int temp = arr[i];
        arr[i] = arr[maxPartent];
        arr[maxPartent] = temp;
        
        heapify(arr, n, maxPartent);
    }

}

void heapify_sort_build(int *arr, int num) {
    int last = num - 1;
    int parent = (last - 1)/2;
    for (int i = parent; i >= 0; i--) {
        heapify(arr, num, i);
    }
}

void heapify_sort_paixu (int *arr, int num) {
    heapify_sort_build(arr, num);
    for (int i = num - 1; i>= 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        heapify_sort_build(arr, i);
        
    }
}

void heapify_sort_start(int *arr, int length) {
//    heapify_sort_build(arr, length);
    heapify_sort_paixu(arr, length);
}