Heap

heap

• 우선순위 큐를 위해 만들어진 자료구조

  • 선입선출하는 일반 큐와 다르게, 우선순위가 높은 데이터가 먼저 나가는 시스템

• 완전 이진 트리의 일종

• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태이다.

• 중복된 값을 허용한다. - 이진트리는 중복값 허용 안됨

• 최대 힙

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

• 최소 힙

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

• 예시

  • 시뮬레이션 시스템

  • 네트워크 트래픽 제어

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

  • 수치 해석적인 계산

• 장점

  • 최대값과 최소값을 찾아낼 때에도 시간복잡도 O(1) 로 가능하다.

  • 삽입과 삭제 연산 시에도 트리의 깊이만큼만 탐색하면 되기 때문에 시간 복잡도가 O(logN) 으로 매우 빠르다.

• 구현

  • 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 그중에서도 힙으로 표현하는 것이 가장 효율적이다.

  • 힙을 저장하는 표준적인 자료구조는 배열

  • 구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.

  • 각 노드와 대응되는 배열의 인덱스틑 불변한다.

  • "부모 노드는 항상 자식 노드보다 우선순위가 높다" 는 조건을 기억하며 완전이진트리 형태로 채워나간다.

최소힙, 최대힙

• 다시 한 번 기억하기

  • "부모 노드는 항상 자식 노드보다 우선순위가 높다" 는 조건을 기억하며 완전이진트리 형태로 채워나간다.

  • 각 노드와 대응되는 배열의 인덱스는 불변한다.

  • 구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.

  • 힙을 저장하는 표준적인 자료구조는 배열

• 성질

  • 왼쪽 자식 인덱스 = 부모 인덱스 * 2

  • 오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1

  • 부모 인덱스 = 자식 인덱스 / 2

참고

• https://velog.io/@yanghl98/자료구조-Heap힙-개념-종류-활용-예시-구현

• https://st-lab.tistory.com/205