Heap Sort-小顶堆实现

heap.cpp

#include <iostream>
#include <cstdlib>
/**
* 小顶堆
*/
void heapInsert(int *heap, int n, int num) {
    int i, j;
    heap[n] = num;
    i = n; 
    j = (n - 1) / 2;
    while(j >= 0 && i != 0) {
        if(heap[j] <= num) {
            break;
        }
        heap[i] = heap[j];
        i = j;
        j = (i - 1) / 2;
    }
    heap[i] = num;
    return;
}

void heapAdjust(int *heap, int top, int n) {
    int j = 2 * top + 1; // 左孩子节点
    int temp = heap[top];
    while(j < n) {
        if(j + 1 < n && heap[j + 1] < heap[j]) {
            j = j + 1;
        }
        if(heap[j] > temp) {
            break;
        }
        heap[top] = heap[j];
        top = j;
        j = 2 * top + 1;
    }
    heap[top] = temp;
}

void heapDelete(int *heap, int n) {
    heap[0] = heap[n - 1];
    heapAdjust(heap, 0, n - 1);
}

void createHeap(int *array, int n) {
    int i;
    for(i = (n - 2) / 2; i >= 0; i--) {
        heapAdjust(array, i, n);
    }
}

// sort 形成的是一个从小到大排列的数组
// 每次都把当前的最大值交换到数组的最后一位，然后对数组剩下的部分进行排序
void heapSort(int *heap, int n) {
    int i, temp;
    for(i = n - 1; i > 0; i--) {
        temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        heapAdjust(heap, 0, i);
    }
}


#define LEN 20

using namespace std;
int main() {
    int heap[LEN];
    int num, i;
    for(int i = 0; i < LEN; i++) {
        heap[i] = rand() % 200;
    }
    createHeap(heap, LEN);
    heapSort(heap, LEN);
    for(int i = 0; i < LEN; i++) {
        cout << heap[i] << " ";
    }
    cout << endl;
    return 0;
}