171107_최소힙

#include <iostream>

#include <algorithm>

using namespace std;

void upheap(int index);

int downheap(int index, int node);

void heap_sort(int node);

void swap(int *a, int *b);

int arr[100000];

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

}

void heap_sort(int node)

{

arr[0] = arr[node];

arr[node] = NULL;

if (node > 2) {

int tmp = 0;

downheap(tmp, node);

}

else //node==2

if (arr[0] < arr[1]) swap(&arr[0], &arr[1]);

}

int downheap(int index, int node)

{

int left = index * 2 + 1;

int right = index * 2 + 2;

if (node == 0 || arr[left] == NULL) return 0;

else if (node - 1 == left)

{

if (arr[index] > arr[left])

{

swap(&arr[index], &arr[left]);

index = left;

}

return 0;

}

else if (node - 1 == right)

{

if (arr[left] < arr[right])

{

if (arr[index] > arr[left])

{

swap(&arr[index], &arr[left]);

index = right;

}

}

else //(arr[left] > arr[right])

{

if (arr[index] > arr[right])

{

swap(&arr[index], &arr[right]);

index = right;

}

}

return 0;

}

else

{

if (arr[left] < arr[right])

{

if (arr[index] > arr[left])

{

swap(&arr[index], &arr[left]);

index = left;

}

}

else //arr[left] > arr[right]

if (arr[index]>arr[right])

{

swap(&arr[index], &arr[right]);

index = right;

}

downheap(index, node);

}

}

void upheap(int index)

{

if (index != 0)

if (index % 2)

{

if (arr[index / 2] > arr[index])

{

swap(&arr[index / 2], &arr[index]);

index /= 2;

upheap(index);

}

}

else

{

if (arr[(index - 1) / 2] > arr[index])

{

swap(&arr[(index - 1) / 2], &arr[index]);

index = (index - 1) / 2;

upheap(index);

}

}

}

int main()

{

int N;

cin >> N;

int node = 0;

int index;

fill(arr, arr + 100000, NULL);

for (int i = 0; i<N; i++)

{

int x;

cin >> x;

if (x == 0)

{

cout << arr[0] << endl;

if (node != 0) node--;

heap_sort(node);

}

else

{

index = node;

arr[node] = x;

node++;

upheap(index);

}

}

}

예외처리 무엇을 빠뜨렸을까..