[자료구조] 알아야 할 자료구조 Heap

Heap

완전 이진 트리 형태의 자료 구조, 말단 노드 레벨을 제외한 내부 노드들이 꽉찬 트리이다.

 

MinHeap, MaxHeap

부모 노드가 자식 노드보다 항상 작으면 MinHeap, 크다면 MaxHeap

우선순위 큐는 Heap으로 구현되어 있다.

Heap을 배열로 구현한다면 parent의 인덱싱을 나누기 방식으로 바로 구할 수 있다.

 

Heapify(node) 연산

node를 루트로 하는 서브 트리가 Heap을 만족할 때까지 트리를 수선하는 것.

void Heapify(int root)
{
	int leftId = GetLeft(root);
	int rightId = GetRight(root);

	if (leftId >= m_Size && rightId >= m_Size)
		return;

	T left = leftId < m_Size ? m_Heap[leftId] : MAX;
	T right = rightId < m_Size ? m_Heap[rightId] : MAX;;

	int smaller = left < right ? leftId : rightId;
	if (m_Heap[root] > smaller)
	{
		std::swap(m_Heap[smaller], m_Heap[root]);
		Heapify(smaller);
	}
}

1. 왼쪽 노드와 오른쪽 노드 중 더 작은 것을 선택한다.

2. 더 작은 노드가 루트 보다 작다면 루트와 교환한다.

3. 더 작은 노드를 기준으로 다시 heapify로 수선한다.

 

HeapSort

힙 자료구조 만들기 : 배열을 받아 똑같은 배열을 생성해주고 내부 노드에 대해 heapify로 수선해준다.

-- BuildHeap pseudo code

template<typename T>
T* BuildHeap(const T* const arr, int size)
{
    T* heap = new T[size]; // size 갯수 만큼 가지는 힙을 생성
    for(int i = 0; i < size; ++i)
    	heap[i] = arr[i]; // 초기화
    
    // 모든 내부 노드에 대해 아래서 부터 수선
    for(int i = size/2; i>=0; --i)
    	heapify(heap, i); // i를 루트로 하는 heap을 수선
 	return heap;
 }
    

 맨 위 Min값 (heap[0])부터 출력하고 배열 맨 뒤를 heap[0]에 할당한 뒤 힙을 만족할 때까지 다시 수선한다.

// 꺼내는 연산
void pop()
{
    Heap[0] = Heap[size-1];
    heapify(0);
    --size;
}

Heapif 연산에 O(logN) 전체 N개 원소를 출력하면 정렬 O(NlogN)안에 가능하다.

 

실제 구현 코드

#pragma once
#include <limits>
#include <algorithm>

template<typename T, size_t MAX_SIZE = 100>
class MinHeap
{
private:
	static constexpr T MAX = std::numeric_limits<T>::max();
	int m_Size = 0;
	T* m_Heap;
public:
	MinHeap()
	{
		m_Heap = new T[MAX_SIZE];
		memset(m_Heap, 0, sizeof(T) * MAX_SIZE);
	}
	~MinHeap()
	{
		delete m_Heap;
	}
	MinHeap(const T* const arr_in, int size)
	{
		if (size > MAX_SIZE) return;

		m_Heap = new T[MAX_SIZE];
		memset(m_Heap, 0, sizeof(T) * MAX_SIZE);
		m_Size = size;

		for (int i = 0; i < size; ++i)
			m_Heap[i] = arr_in[i];

		// build heap
		for (int i = size / 2; i >= 0; --i)
			Heapify(i);
	}
private:
	int GetLeft(const int& i) { return 2 * i + 1; }
	int GetRight(const int& i) { return 2 * i + 2; }
	int GetParent(const int& i) { return (i-1) / 2; }
	void Heapify(int root)
	{
		int leftId = GetLeft(root);
		int rightId = GetRight(root);

		if (leftId >= m_Size && rightId >= m_Size)
			return;

		T left = leftId < m_Size ? m_Heap[leftId] : MAX;
		T right = rightId < m_Size ? m_Heap[rightId] : MAX;;

		int smaller = left < right ? leftId : rightId;
		if (m_Heap[root] > smaller)
		{
			std::swap(m_Heap[smaller], m_Heap[root]);
			Heapify(smaller);
		}
	}
public:
	int top() const { return m_Heap[0]; }
	void push(T data)
	{
		if (m_Size == MAX_SIZE)
			return;

		m_Heap[m_Size++] = data;

		int cur = m_Size - 1, parent = GetParent(cur);
		while (cur != 0 && m_Heap[parent] > m_Heap[cur])
		{
			std::swap(m_Heap[parent], m_Heap[cur]);
			cur = parent;
			parent = cur / 2;
		}
	}
	void pop()
	{
		if (m_Size == 0)
			return;

		m_Heap[0] = m_Heap[m_Size-1];
		Heapify(0);
		--m_Size;
	}
};

 

테스트

#include "heap.h"
#include <iostream>
int main()
{
	srand((unsigned int) time(NULL));
	MinHeap<int, 100> heap;
	
	int arr[100] = {};
	for (int i = 0; i < 100; ++i)
		arr[i] = i;

	std::random_shuffle(arr, arr + 100);
	for (int i = 0; i < 100; ++i)
		heap.push(arr[i]);

	for (int i = 0; i < 100; ++i)
	{
		printf("%d\n", heap.top());
		heap.pop();
	}

	const char* name = "skdfweklqnflakjjqiaknxqwzxalknpoirtmza";
	int len = strlen(name);
	MinHeap<char, 100> heap_str(name, len);

	// sorted string
	for (int i = 0; i < len; ++i)
	{
		printf("%c", heap_str.top());
		heap_str.pop();
	}
	printf("\n");

	return 0;
}