#include<iostream>
#include "heap.h"

using namespace std;

void __shiftDown(int arr[],int n,int k){
    //2*k+1 left child ,parent(i)=(i-1)/2
    while (2*k+1<n){
        int j=2*k+1;
        if(arr[j+1]>arr[j] && j+1<n){
            j++;
        }

        if (arr[k]>arr[j]){ break;}

        swap(arr[k],arr[j]);
        k=j;
    }
}
void heapSort2(int arr[],int n){
    MaxHeap<int> maxheap=MaxHeap<int>(arr,n);
    for(int i=n-1;i>=0;i--){
        arr[i]=maxheap.extractMax();
    }
}

void heapSort1(int arr[],int n){
     MaxHeap<int> maxHeap =MaxHeap<int>(n);

    for (int i = 0; i <n; i++) {
        maxHeap.insert(arr[i]);
    }

    for(int i=n-1;i>=0;i--){
        arr[i] = maxHeap.extractMax();
    }

}

//place heap sort
void heapSort3(int arr[],int n){
    //arr[0...n-1],hepify
    for(int i=(n-1-1)/2;i>=0;i--){
        __shiftDown(arr,n,i);
    }

    for(int i=n-1;i>0;i--){
        swap(arr[0],arr[i]);
        __shiftDown(arr,i,0);
    }
}

int main() {
    int arr[]={1,3,5,2,4,6,9,8,7};
    int n=9;

    //hepasort2

    heapSort3(arr,n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<",";
    }
    cout<<endl;


    return 0;
}

#ifndef SORT_HEAP_H
#define SORT_HEAP_H

#include <iostream>
#include <cassert>

using namespace std;

template<typename Item>
class MaxHeap {
private:
    Item *data;
    int count;
    int capacity;

    //data[1...n]
    void shiftUp(int k) {
        while (k > 1 && data[k / 2] < data[k]) {
            swap(data[k / 2], data[k]);
            k /= 2;
        }
    }

    void shiftDown(int k) {
        while (2 * k <= count) {
            int j = 2 * k;

            if (j + 1 <= count && data[j + 1] > data[j]) {
                j++;
            }

            if (data[k] >= data[j]) {
                break;
            }
            swap(data[k], data[j]);
            k = j;
        }
    }

public:

    MaxHeap(int capacity) {
        data = new int[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

    MaxHeap(int arr[], int n) {
        data = new int[n + 1];
        capacity = n;

        for (int i = 0; i < n; i++) {
            data[i + 1] = arr[i];
        }
        count = n;
        //data[1...count]
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }

    }

    ~MaxHeap() {
        delete[] data;
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;

    }

    void insert(Item item) {
        assert(count + 1 <= capacity);
        data[count + 1] = item;
        shiftUp(count + 1);
        count++;
    }

    int extractMax() {
        assert(count > 0);
        Item ret = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return ret;
    }

};

#endif //SORT_HEAP_H