자료구조 - 힙

알아야 할 사전 지식

우선순위 큐를 위하여 만들어진 자료구조 이다.

 

우선순위 큐란?

우선순위의 개념을 큐에 도입한 자료 구조

데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

 

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

 

우선순위 큐는 어디에 사용하는가?

1. 시뮬레이션 시스템

2. 네트워크 트래픽 제어

3. 운영 체제에서의 작업 스케줄링

4. 수치 해석적인 계산

 

우선 순위 큐는 배열, 연결리스트, 힙으로 구현 가능하지만 힙으로 구현하는 것이 가장 효율적이다.

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

 

Heap 이란?

- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

- 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

  - 큰 값이 상위 레벨, 작은 값이 하위 레벨에 있는 정도 

  - 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리

 

Heap의 종류

(1) 최대 힙(max heap)

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

 

(2) 최소 힙(min heap)

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

 

Heap 구현하기

- 힙을 저장하는 표준 자료구조는 배열

- 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 제외

- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 x ex) 루트 노드의 오른쪽 노드 번호는 항상 3

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

    - 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 

    - 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1

    - 부모의 인덱스 = (지식의 인덱스) / 2

 

 

Heap 삽입

(1) 힙에 새로운 요소가 들어올시, 새로운 노드를 힙의 마지막 노드에 이어서 삽입

(2) 새로운 노드를 부모 노드들과 교환해서 힙의 성질 만족

Heap 삭제

(1) 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제

     - 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.

(2) 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

(3) 힙을 재구성

 

참고 블로그 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html