Heap

안녕하세용

방금 전 stack과 queue를 끝냈습니당 !

오늘은 Heap에 대해 집중 탐구 해 볼 예정입니당

 

힙에 대해 알기 전, 우리는 우선 순위 큐를 알아야합니다.

 

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

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

 

해당 글을 보고 작성을 하였습니다! (작성자님 감사합니다 !!)

 

우선순위 큐 Priority Queue

 

우선 순위 큐란, 우선순위의 개념을 큐에 도입한 자료구조입니다. 데이터들이 우선순위를 가지고 있고 우선 순위가 높은 데이터들이 먼저 나갑니다.

 

자료구조	삭제되는 요소
스택 (Stack)	가장 최근에 들어온 데이터
큐 (Queue)	가장 먼저 들어온 데이터
우선 순위 큐(Priority Queue)	가장 우선 순위가 높은 데이터

 

우선 순위 큐의 이용사례는 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥴링 등 우선 순위에 따라 처리해야하는 데이터들에 사용됩니다.

 

이러한 우선 순위 큐는 배열, 연결리스트, 힙으로 구현이 가능합니다. 그 중 힙으로 구현하는 것이 가장 효율적입니다.

우선 순위 큐를 구현하는 방법	삽입	삭제
순서 없는 배열	O(1)	O(N)
순서 없는 연결 리스트	O(1)	O(N)
정렬된 배열	O(N)	O(N)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

 

그렇다면 자료구조 힙에 대해 알아봅시다.

 

Heap

정의

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. -> 큰 값이 상위레벨 작은 값이 하위 레벨에 있는 정도
• 힙 트리에서 중복된 값을 허용한다. (이진 트리에서는 중복된 값을 허용하지 않음)

종류

• 최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

 

• 최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

구현

 

• 힙을 저장하는 표준적인 자료 구조는 배열이다.
• 구현을 쉽게 하기 위해서 배열의 첫번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 예를들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.

 

힙에서 부모노드와 자식노드의 관계

 

• 왼쪽 자식의 인덱스 = (부모 인덱스) X 2
• 오른쪽 자식의 인덱스 = (부모 인덱스) X 2 + 1
• 부모 인덱스 = (자식 인덱스) / 2

삽입

 

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

아래는 최대힙에 새로운 요소 8을 삽입하는 예시이다.

삭제

최대 힙을 예로 들어서 설명하면, 우선 여기서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.

1. 최대 힙에서 최댓 값은 루트 노드이므로 루트노드가 삭제된다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.