HEAP TREE with HEAP SORT ALGORITHM

linear linked list를 이용한 stack에 이어 두번째 algorithm 시간이다.

오늘은 heap tree와 heap sort를 구현했다.

 

재학시절 트리를 구현한 적이 있긴 있는데

2년이 넘도록 그에 관련한 알고리즘을 사용하지도 않고 보지도 않았으니 다 까먹었다.

그래서 heap tree를 이해하는데 한참이 걸렸다.

아무것도 모르는 사람이 heap tree 의 이미지를 보면 난해할것이다.

이미지만 보고서 구현을 할라면 무엇으로 구현을 해야하는지 착잡해지는데.

간단하다.

heap tree는 1차원 배열로 구현되며,

0이 아닌 1로 시작한다는 가정 하에 부모 자식간의 상관은

자식/2가 부모를 가리킨다.

이렇게 말이다.

 

 

#include <iostream>
#include <stdlib.h>
#include <math.h>

void newKey();
void delKey();
void sortKeys();
void showKeys(int *arr);
void swap(int *arr, int k1, int k2);

int *heap;

int main() {
	int a;
	heap = NULL;
	while (true) {
		std::cout << " 1.New key\n 2.Delete a Key\n 3.Sort Keys\n 4.Show keys\n 5.EXIT\n>>";
		std::cin >> a;
		switch (a) {
		case 1:
			newKey();
			break;
		case 2:
			delKey();
			break;
		case 3:
			sortKeys();
			break;
		case 4:
			showKeys(heap);
			break;
		case 5:
			delete(heap);
			return 0;
		}
	}
	return 0;
}

void newKey() {
	int value,key;
	std::cout << "input a new value for key\n>>";
	std::cin >> value;
	if (heap == NULL)
		heap = new int[1]{ value };
	else {
		heap = (int*)realloc(heap, _msize(heap) + sizeof(int));
		key = _msize(heap) / sizeof(int)-1;
		heap[key] = value;
		while (key > 1) {
			if (heap[key] < heap[(key + 1)/ 2 - 1]) {
				swap(heap, key, (key + 1)/ 2 - 1);
				key = (key+1)/2-1;
			}
			else
				break;
		}
	}
}


void delKey() {
	int key = 0, tmpkey;
	swap(heap, key, _msize(heap) / sizeof(int) - 1);
	showKeys(heap);
	std::cout << _msize(heap) / sizeof(int) - 1 << std::endl;
	heap = (int*)realloc(heap, _msize(heap) - sizeof(int));
	std::cout << _msize(heap) / sizeof(int) - 1 << std::endl;

	while ((key+1)*2-1 <= _msize(heap) / sizeof(int) - 1) {
		if ((key + 1) * 2 > _msize(heap) / sizeof(int) - 1 && heap[key] > heap[(key+1)*2-1]) {
			swap(heap, key, (key + 1) * 2 - 1);
			break;
		}
		else if ((key + 1) * 2 > _msize(heap) / sizeof(int) - 1) break;
		else {
			if (heap[(key + 1) * 2 - 1] < heap[(key + 1) * 2]) {
				tmpkey = (key + 1) * 2 - 1;
			}
			else
				tmpkey = (key + 1) * 2;
			if (heap[key] > heap[tmpkey]) {
				swap(heap, key, tmpkey);
				key = tmpkey;
			}
			else break;
		}
	}
}

void sortKeys() {
	int len = _msize(heap) / sizeof(int);
	int *tmp = new int[len];
	for (int i = 0; i < len; i++) {
		tmp[i] = heap[i];
		int key = i;
		while (key > 0) {
			if (tmp[key] > tmp[(key + 1) / 2 - 1]) {
				swap(tmp, key, (key + 1) / 2 - 1);
				key = (key + 1) / 2 - 1;
			}
			else
				break;
		}
	}
	for (int i = len - 1; i > 0;) {
		swap(tmp, 0, i--);
		int key=0, tmpKey;
		while ((key + 1) * 2 - 1 <= i) {
			if ((key + 1) * 2 > i && tmp[(key + 1) * 2 - 1] > tmp[key]) {
				swap(tmp, key, (key + 1) * 2 - 1);
				break;
			}
			else if ((key + 1) * 2 > i) break;
			else {
				if ((tmp[(key + 1) * 2 - 1]) > tmp[(key + 1) * 2]) tmpKey = (key + 1) * 2 - 1;
				else tmpKey = (key + 1) * 2;
				swap(tmp, key, tmpKey);
				key = tmpKey;
			}
		}
		showKeys(tmp);
	}
	for (int i = 0; i < len; i++)
		heap[i] = tmp[i];
	delete(tmp);

}

void showKeys(int *arr) {
	int row;
	for (row = 1; ; row++) {
		if (_msize(arr) / sizeof(int) < pow(2, row))
			break;
	}
	for (int i = 0; i < _msize(arr) / sizeof(int); i++) {
		if ((float)log2(i+1) - (int)log2(i+1) == 0) {
			for (int j = 0; j < pow(2, row-1)-1; j++)
				std::cout << "  ";
		}
		if (arr[i] < 10)
			std::cout << " ";
		std::cout << arr[i];
		for (int j = 0; j < pow(2, row)-1; j++)
			std::cout << "  ";
		if ((float)log2(i + 2) - (int)log2(i + 2) == 0) {
			std::cout << std::endl;
			row--;
		}
	}
	std::cout << std::endl;
}

void swap(int *arr, int k1, int k2) {
	int value = arr[k1];
	arr[k1] = arr[k2];
	arr[k2] = value;

 

머리가 좋지 않아서 구현하는데 시간이 걸렸다.

특히 delete함수를 구현했지만 멍청하게 해서 자괴감이 들었다.

혼자 배우며 어떠한 서적도 참고하지 않는 공부라서

위 코드로 실행하면 버그가 생기는 부분이 여러군데 있을지도 모르겠다.

 

배우며 느낀것은

나는 멍청하다.

 

태클 환영.