c - 了解堆

Question

我查看的每篇关于堆的引用资料都说构建堆的 sift_down 方法是理想的方法，但这是否意味着仍然可以使用 sift_up 构建堆？如果是这样，为什么 sift_down 是首选？我正在尝试通过我正在学习的算法类(class)更好地理解这些类型的事物。我想尝试实现一个使用 sift_up 的 build_heap 函数，但到目前为止我还没有任何运气，尽管我已经设法使用 sift_down 让它工作。

任何人都可以分享任何想法、建议或引用？这是我目前正在苦苦挣扎的一些功能:

#include <stdio.h>

void bottom_up_heapsort(int*, int);
void heapsort(int*, int);
void sift_up(int*, int);
void sift_down(int*, int);
void build_max_heap(int*, int); 
void bottom_up_build_max_heap(int*, int);
void swap(int*, int*);

int heapsize;

int main() {
    int A[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9 };
    int B[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9 };
    int i;
    int size = 9;

    printf("Unsorted array: \n");
    for(i = 0; i < size; i++) {
        printf(" %d ", A[i]);
    }

    heapsort(A, size); 
    printf("\n");

    printf("Sorted array: \n");
    for(i = 0; i < size; i++) {
        printf(" %d ", A[i]);
    }
    printf("\n");

    printf("----------------------------------\n");
    printf("Unsorted array for bottom up: \n");
    for(i = 0; i < size; i++) {
        printf(" %d ", B[i]);
    }

    bottom_up_heapsort(B, size); 
    printf("\n");

    printf("Sorted array: \n");
    for(i = 0; i < size; i++) {
        printf(" %d ", B[i]);
    }
    printf("\n");

    return 0;
}

void bottom_up_heapsort(int* arr, int len) {
    int i;

    bottom_up_build_max_heap(arr, len);
    for(i = len-1; i >= 1; i--) {
        sift_up(arr, len);
        heapsize--;
        swap(&arr[i], &arr[0]);
    }
}

void heapsort(int* arr, int len) {
    int i;

    build_max_heap(arr, len);

    for(i = len-1; i >= 1; i--) {
        swap(&arr[0], &arr[i]); // move arr[0] to its sorted place
        heapsize = heapsize - 1;
        sift_down(arr, 0);  // repair the heap
    }
}

void sift_down(int* arr, int i) {
    int l = 2*i, r = 2*i+1;
    int largest;

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

    if(r < heapsize && arr[r] > arr[largest]) {
        largest = r;
    }

    if(largest != i) {
        swap(&arr[i], &arr[largest]);
        sift_down(arr, largest);
    }
}

void sift_up(int* arr, int i) {
    if(i == 1) return; // at the root

    if(arr[i] > arr[i/2]) {
        swap(&arr[i], &arr[i/2]);
        sift_up(arr, i/2);
    }
}

void bottom_up_build_max_heap(int* arr, int len) {
    heapsize = len;
    int i;
    for(i = 0; i <= len; i++) {
        sift_up(arr, i);
    }
}

void build_max_heap(int* arr, int len) {
    heapsize = len;
    int i;
    for(i = len/2; i >= 0; i--) {
        // invariant: arr[k], i < k <= n are roots of proper heaps
        sift_down(arr, i);
    }
}

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

Answer 1

你应该可以做到

for (int i = 1; i <= n; i++) sift_up(heap, i);

相当于一个一个插入元素。最坏情况下的运行时间是 Theta(n log n)，因为在最坏情况下，每个新元素都必须一直筛选到根。这个运行时间比 sift_down heapify，即 Theta(n) 差。不同之处在于 sift_down 只能将大多数元素向下移动几个级别，而 sift_up 可以将大多数元素向上移动 log n 级别。