c-使用heapfy将最大堆转换为最小堆

Question

我正试图将我得到的最大堆堆成最小堆。由于某种原因，我没有得到我期望的结果。

我已经构建了我的最大堆，它的数组内容如预期所示：

60 50 30 20 40 10

当尝试堆积上面的数组并将其转换为最小堆时，所需的结果是：

10 20 30 60 50 40

然而，我得到的结果是：

10 20 60 50 40 30

以下是我的功能：

struct _heap
{
int max; //array max
int pos; //current position
int* priority; //array gets initialized after.
};
typedef struct _heap heap_t;
void heapify_min(heap_t* h, int father)
{
int smallest = father;
int left = 2 * father + 1;
int right = 2 * father + 2;
if (left < h->pos && h->priority[left] < h->priority[smallest) {
smallest = left;
}
if (dir < h->pos && h->priority[right] < h->priority[smallest])
smallest = right;
if (smallest != father) {
swap(father,smallest,h->priority);
heapify_min(h,left);
}
}
void swap(int a, int b, int *v)
{
int f = v[a];
v[a] = v[b];
v[b] = f;
}

void build_heap(heap_t* h)
{
int n = h->pos;
int i2 = (n/2) -1;
int i;
for (i = i2;i>=0;i--) {
heapify_min(h,i);
}
}

任何见解都会非常有用。

Answer 1

对照我的代码检查您的代码(下面是min_heap的工作代码(。有3个问题：

1. 在heapify_min函数中，当您递归调用函数时，您应该使用变量最小，而不是左。

2. 在MIN HEAP中比较值的运算符应该>(更大(而不是<(较小(

3. 函数build_heap是正确的，但这应该只是数组的第一次重排。在第一次重新排列数组(第一次创建最大堆(之后，应该交换数组中的第一个和最后一个元素。在初始交换之后，您可以继续使用heapify函数，但每次进一步创建最大堆时，都会在循环中交换子树中的值(在递归调用期间(，并用最后一个元素交换第一个元素，直到只剩下一个节点为止。

这里是代码：

void heapify(int arr[], int n, int i)
{
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
// If left child is larger than root
if (l < n && arr[l] > arr[smallest])
smallest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[smallest])
smallest = r;
// If largest is not root
if (smallest != i) {
//swap
int backUp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = backUp;
// Recursively call on heapify function
heapify(arr, n, smallest);
}
}
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Swap root node with last node in array (WARNING: last node don't have to be 
necessarily smallest one)
int backUp = arr[0];
arr[0] = arr[i];
arr[i] = backUp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("n");
}