ヒープソート

ヒープソート.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
typedef vector<int> vi;
const int INF = INT_MAX;

const int SIZE = 13;

vi heap(SIZE, INF);
int num = 0; //heapに入っている個数

void make_heap(int pos) {
    // addするときに親のノードが子のノードより大きくなるように再編成？
    if(heap[pos >> 1] < heap[pos]){
        swap(heap[pos >> 1], heap[pos]);
        make_heap(pos >> 1);
    }
}

void add(int x) { //追加
    num++;
    heap[num]=x;
    make_heap(num);
}

void update(int pos) {
    if((pos << 1 | 0) <= num && heap[pos << 1 | 0] > heap[pos]) {
        swap(heap[pos << 1 | 0], heap[pos]);
        update(pos << 1 | 0);
    }
    if((pos << 1 | 1) <= num && heap[pos << 1 | 1] > heap[pos]) {
        swap(heap[pos << 1 | 1], heap[pos]);
        update(pos << 1 | 1);
    }
}

void heap_del() {
    // 一番上のノードを削除
    swap(heap[1], heap[num]);
    num--;
    update(1);
}

int main() {

    vi v{3, 5, 10, 2, 7, 11, 6, 2, 6, 8, 3, 1}; // SIZE-1個
    for(int i = 0; i< SIZE; i++) {
        add(v[i]);
    }
    for(int i = 0; i< SIZE; i++) {
        heap_del();
    }
    for(int i = 1; i<= SIZE; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");

    for(int i = 1; i< SIZE/2; i++) {
        swap(heap[i], heap[SIZE - i + 1]);
    }

    for(int i = 1; i<= SIZE; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}