堆调整算法

堆调整算法

思路

算法将获取到一组数据的最大值(针对大顶堆)或最小值(针对小顶堆)。

基本思想

通过堆排序的调整算法获取到最大值和最小值。

效率

时间复杂度: o(logn)
空间复杂度: o(1)

应用

1. 获取最大值或最小值
2. top K

代码实现

递归实现

// C++
void Swap(int &first, int &second) {
    int temp    = first;
    first       = second;
    second      = temp;
}

// start->index start, end->index end
void AdjustHeap(int array[], int start, int end) {
    int left_child  = start * 2 + 1;
    int right_child = start * 2 + 2;
    int temp        = start;

    if (start <= end / 2) { // not leaf
        // find max(temp, left_child)
        if (left_child < end && array[temp] < array[left_child]) {
            temp    = left_child;
        }
        // find max(temp, right_child)
        if (right_child < end && array[temp] < array[right_child]) {
            temp    = right_child;
        }
        // temp has change, should adjust
        if (temp != start) {
            Swap(array[temp], array[start]);
            AdjustHeap(array, temp, end);
        }
    }
}

非递归实现

// C++
// start->index start, end->index end
void AdjustHeap(int array[], int start, int end) {
    int temp    = array[start];

    for (int index = start * 2 + 1; index <= end; index = index * 2 + 1) {
        // find max(left_child, right_child)
        if (index < end && array[index] < array[index + 1]) {
            index++;
        }
        // find max(child, temp)
        if (temp > array[index]) {
            break;
        }
        // move child to parent
        array[start]    = array[index];
        start           = index;
    }

    array[start] = temp;
}