힙 ( Heap )

( 본 게시글은 작성자가 메모용으로 사용하는 용도임을 밝힙니다. 정보가 불확실할 수 있으니 참고 부탁드립니다 )

 

힙 ( Heap )이란 완전 이진 트리의 형태로 이루어진 자료구조로 우선순위 큐를 위해 만들어졌다.

우선순위 큐란 데이터를 삭제할때 데이터의 우선순위를 매겨 우선순위대로 데이터가 삭제되는 자료구조이다. 기존에 스택은 데이터가 가장 늦게 들어온순대로 삭제를 하고 일반 큐는 선입선출의 원리로 삭제를 하지만, 우선순위 큐는 들어온 순서에 상관없이 일정 규칙에 따라 데이터의 삭제가 진행된다. 우선순위 큐는 연결리스트, 배열 등으로도 구현이 가능하지만 힙으로 구현하는게 제일 효율적이다.

힙의 특징으로는 힙은 반정렬 상태를 유지한다는 것이다. 큰 값이 상위에 존재하고, 작은 값이 하위에 존재하는 완전 이진트리의 상태를 말할 수 있다. 그리고 저번에 배운 이진 탐색 트리와는 다르게 힙은 중복된 값을 허용한다. 

힙에는 두가지 종류가 있는데, 최대 힙, 최소 힙 두가지로 나눌 수 있다. 최대 힙은 부모 노드가 가장 큰 값의 노드가 오는 완전 이진 트리이고, 최소 힙은 부모 노드가 가장 작은 값의 노드가 오는 완전 이진 트리이다. 보통 힙이라고 하면 최대 힙을 다룬다.

이러한 힙은 최댓값이나 최솟값을 빠르게 찾아내는데에 유리한 자료구조이다.

위의 7개의 값이 있다고 하고, 이것을 최대 힙의 구조로 만들어본다고 하면, 과정은 값 삽입 -> 노드 힙 구조로 정렬이 반복 된다.

힙은 완전 이진 트리의 형태를 가지고 있기 때문에, 왼쪽 자식 노드부터 추가가 되는데, 이때 힙의 구조가 깨지지 않도록 매번 정렬을 해준다.

먼저 5를 삽입하여 5가 루트 노트가 된 형태다.

다음으로 2를 삽입할때 2는 5보다 작기때문에 왼쪽에 삽입해도 힙 구조가 깨지지 않는다. 하지만 6을 오른쪽에 삽입하면 최대 힙의 구조가 깨지기 때문에, 5와 6을 스왑해줄 필요가 있다. 

스왑이 완료된 후의 모습이다. 힙을 사용할때는 항상 힙 구조( 예시는 최대 힙 )가 깨지지 않도록 값을 삽입할때마다 재정렬을 해줘야 한다. 이러한 규칙 아래 모든 값을 삽입하고 나면 다음과 같은 구조가 될 것이다.

다음과 같은 최대 힙의 경우에는 최댓값을 찾을 때 바로 루트 노드에 접근하면 되기 때문에, 최댓값, 최솟값 탐색에 매우 빠른 구조라고 할 수 있다.

 

힙을 구현할때는 표준적으로 배열을 사용한다. 배열을 선언하고 초기 선언할때 배열이 꽉차면 그때마다 배열의 크기를 증설시켜주면서, 정렬할때 값을 스왑하는 방식으로 사용한다.

여기서 구조체 Node는 값을 매개변수로 하는 재정의 생성자로 선언되었고, Heap이라는 함수를 선언하여, 힙을 배열을 사용하여 크기를 설정해주도록 한다. Parent와 LeftChild는 부모와 왼쪽 자식노드의 인덱스를 반환하는 함수다 ( 오른쪽 자식노드는 왼쪽 자식에 +1 을 하면 됨 ). 그리고 RemoveMin은 값을 정렬할때 사용하는 함수로, 함수 내의 while문에서 selected로 Swap을 할 노드를 설정해주고, 무한루프를 통해 정렬을 반복한다. 탈출 조건은 왼쪽 자식 노드의 인덱스번호가 size보다 같거나 크고, 선정된 노드의 데이터값이 해당 부모의 데이터 값보다 작다면 최대 힙의 구조가 유지되는 것이기 때문에, 탈출된다.

먼저 힙을 구현할 배열의 크기를 3으로 설정한다.

다음 구조체 heap의 멤버인 함수 Insert로 해당 값들을 삽입한다.

이후 while문으로 힙의 사이즈가 0이 될때까지 RemoveMin을 통해 값을 제거하여 재정렬한다. ( 해당 예시에서는 값 자체는 삭제되지 않고, 출력만 하지않게 설정함 )

콘솔창에 출력하면 다음과 같이 출력되고, 매 줄마다 최대 힙의 최댓값인 루트 노드의 값이 제거되면서 매번 정렬이 일어나는 것을 볼 수 있다.

값 삽입이 완료된 후의 구조는 다음과 같을 것이고, 삭제되는 순서는 최댓값부터 제거된다. 제거될때마다 힙은 정렬을 매번 일으킨다. 해당 예시에서는 가장 마지막 인덱스의 노드와 루트 노드가 값을 스왑하고, 힙 구조에 맞게 다시 스왑을 하며 정렬한다 ( 스왑 이후 마지막 인덱스의 노드는 출력하지 않게끔 설정 ).

 

자료 참조 : https://todaycode.tistory.com/56

힙(Heap) 이란?

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog