[Data Structure] C++로 나만의 힙 구현하기

다익스트라 알고리즘을 공부하다가 성능을 향상시키려면 우선순위 큐를 이용하면 된다는 것을 알게 되었다. 우선순위 큐의 기반이 되는 힙 자료구조를 구현해보았다.

#include <iostream>
#define SWAP(a, b) {int temp = a; a = b; b = temp;}

int heap[100] = { 0, };

int heapSize = -1;

void push(int data) {
	heap[++heapSize] = data;
	for (int index = heapSize; index > 0; index = (index - 1) / 2) {
		if (heap[index] > heap[(index - 1) / 2]) {
			SWAP(heap[index], heap[(index - 1) / 2]);
		}
	}
}

int pop() {
	int rootNode = heap[0];
	
	heap[0] = heap[heapSize];
	heap[heapSize--] = 0;

	int index = 0;

	while (true) {
		int prev = index;
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		if (left <= heapSize && heap[index] < heap[left]) {
			index = left;
		}
		if (right <= heapSize && heap[index] < heap[right]) {
			index = right;
		}
		if (index != prev) {
			SWAP(heap[index], heap[prev]);
		}
		else {
			break;
		}
	}

	return rootNode;
}

int main() {
	push(2);
	pop();
}