[자료구조] MAXHEAP: 최대힙

2020. 6. 2. 17:56Algorithm/basic

Heap 간단설명

자료구조 Heap은 이진트리로, 삽입/삭제할 때 모두 O(logn)이 걸린다.

Heap은 Priority Queue를 도입한 자료구조로, 여러 데이터가 주어질 때, 최댓값과 최솟값을 빠르게 찾고 싶을 때사용한다.

Binary Search Tree와 다르게 Heap은 중복값을 허용하는 것을 기억해두자.

Heap은 기본적으로 배열로 나타낼 수 있다. priority queue 관련된 라이브러리를 활용해서 나타낼 수 있다.

배열로 표현할 때 인덱스 번호로 노드를 비교할 것이기 때문에 heap으로 구현한 배열에서 인덱스 0은 안 쓴다!

  • 부모노드 INDEX = 자식노드 INDEX / 2

  • 왼쪽자식노드 INDEX = 부모노드 INDEX * 2

  • 오른쪽자식노드 INDEX = 부모노드 INDEX * 2 + 1

최대힙

부모노드의 key 값 >= 자식노드의 key

최대힙에서 노드 추가

  1. 배열의 마지막INDEX에 새로운 데이터를 할당한다.

  2. 추가된 노드에 대한 부모 노드를 찾고, 부모노드의 값보다 추가된 노드의 값이 크면 두 노드의 위치를 서로 바꾼다.

  3. 최상단 루트(root)노드까지 다 비교해본다. 이를 위해서 자식노드INDEX에 2를 나눈 값이 부모노드INDEX가 되기 때문에 자식노드INDEX는 루트노드INDEX, 즉 1보다는 커야한다!

최대힙에서 노드 삭제

  1. 루트노드INDEX, 즉 인덱스 1에 있는 값은 삭제한다. 이때 배열에서 값이 삭제되지 않고 맨 마지막에 있는 노드와 자리를 바꾸는 것이다. 대신 Heap size(hidx)를 1만큼 줄여줘야한다.

  2. 자식노드가 2개일 때 자식노드끼리 비교하여 최댓값을 가진 노드를 결정한다.

  3. 자식노드와 부모노드를 비교하여, 자식노드가 더 큰 값을 가지면 두 노드의 위치를 바꾼다.

  4. 자식노드INDEX가 Heap size(hidx)보다 작거나 같을 때까지 2,3번 과정을 반복한다.

'Algorithm > basic' 카테고리의 다른 글

이분 탐색 (Parametric Search)  (0) 2020.07.22