cxfans
9/9/2019 - 7:25 AM

堆排序 #Algorithm

堆排序 #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;
}