堆排序 #Algorithm
#define ElemType int
void Swap(ElemType *a, ElemType *b) {
ElemType t;
t = *a;
*a = *b;
*b = t;
}
void AdjustDown(ElemType A[], int k, int len) {
A[0] = A[k];
for (int i = k * 2; i <= len; i *= 2) {
if (A[i + 1] > A[i] && i < len) i++;
if (A[0] > A[i]) break;
else {
A[k] = A[i];
k = i;
}
}
A[k] = A[0];
}
void AdjustUp(ElemType A[], int k) {
A[0] = A[k];
int i = k / 2;
while (i > 0 && A[i] < A[0]) {
A[k] = A[i];
k = i;
i = k / 2;
}
A[k] = A[0];
}
void BuildMaxHeap(ElemType A[], int len) {
for (int i = len / 2; i > 0; i--) {
AdjustDown(A, i, len);
}
}
void HeapSort(ElemType A[], int len) {
BuildMaxHeap(A, len);
for (int i = len; i > 1; i--) {
Swap(&A[i], &A[1]);
AdjustDown(A, 1, i - 1);
}
}
#include <stdbool.h>
bool IsMinHeap(ElemType A[], int len) {
if (len % 2 == 0) {
if (A[len / 2] > A[len]) return false;
for (int i = len / 2 - 1; i >= 1; i--) {
if (A[i] > A[2 * i] || A[i] > A[2 * i + 1])return false;
}
} else {
for (int i = len / 2; i >= 1; i--) {
if (A[i] > A[2 * i] || A[i] > A[2 * i + 1]) return false;
}
}
return true;
}