C++ 배열로 구현한 최대 힙 (Array MaxHeap C++ )

배열로 구현한 최대힙 

구현의 편의상 1번째 인덱스부터 사용함, 삭제된 인덱스 값은 0

maxheap:: 자식관계와 상관없이 부모노드가 자식노드보다 큰 구조 (완전 이진트리)

힙생성(heapify)의 시간복잡도:: O(logN) 트리의 높이에 따라

/* 자료구조 최대힙 구현(배열) - 2019/12/29 xtar.tistory */
#include <iostream>
using namespace std;

//최대힙 메소드
void Make_MaxHeap(int arr[],int size)
{
	int cnt = 0;

	for (int i = 0; i < size; i++)
	{
		int child = i;
		int parent = child / 2;

		while (arr[parent]<arr[child] && child>1)
		{
			auto a = arr[parent];
			arr[parent] = arr[child];
			arr[child] = a;

			child = parent;
			parent = child / 2;
		}
	}
}
//최대힙 삭제 메소드
int Pop_MaxHeap(int arr[], int size)
{
	int answer = arr[1];
	int tmp = arr[size];

	int parent = 1;
	int child = 2;

	while (child<size)
	{
		if (arr[child] < arr[child + 1])
			child++;
		if (arr[1] > arr[child])
			break;

		arr[parent] = arr[child];
		parent = child;
		child *= 2;
	}
	arr[parent] = arr[size];
	arr[1] = 0;
	return answer;
}
int main()
{
	int arr[10] = {0,3,8,13,16,11,5,2,1,33};
	int size = sizeof(arr) / sizeof(int);
	
	Make_MaxHeap(arr, size);

	for (auto x : arr)
	{
		cout << x << " ";
	}
	cout << endl;

	cout << Pop_MaxHeap(arr, size) << endl;
	for (auto x : arr)
	{
		cout << x << " ";
	}
	return 0;
}