我查看的每篇关于堆的引用资料都说构建堆的 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;
}
最佳答案
你应该可以做到
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 级别。
关于c - 了解堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26345046/