c - 为什么我的函数按升序而不是最小堆对元素进行排序？

Question

我插入的数字是:

37 25 43 65 48 84 73 18 79 56 69 32.

但是我的号码显示为

18 25 32 37 48 43 73 65 79 56 69 84

即升序。

应该是一个最小堆，顺序为

18 37 32 25 48 43 73 65 79 56 69 84

(我在纸上进行计算后的顺序)。有人能告诉我如何修复我的函数，使其成为最小堆并且不会给我一些奇怪的顺序吗？

void siftUp(int heap[], int n) {
// Sift the value in heap[n] so that heap[1..n] is a heap
int siftItem = heap[n];
int child = n;
int parent = child / 2;
while (parent > 0) {
    if (siftItem >= heap[parent]) {
        break;
    }
    heap[child] = heap[parent];         // Move the parent down
    child = parent;
    parent = child / 2;
}
heap[child] = siftItem;
}

Answer 1

一个明显的问题 -- C 数组是基于 0 而不是基于 1 的，因此您的父计算相差 1。它应该是 parent = (child - 1)/2。