[Basic Java] Heap

Heap 이란?

• 자료구조 힙
• Java 메모리 영역 (완전 다른 개념 / 스택도 있음)

우선순위를 정할 때 효율적인 알고리즘이다.
예를 들어서 운영체제 OS 에서 프로세스들이 우선순위를 부여해 작업을 처리하는 경우, CPU 나 다른 자원을 무겁게 사용하면서 며칠 동안 수행해야 할 작업이 있다면 다른 작업들의 동작을 방해할 수 있으므로 우선순위를 낮춰 작업을 할 수 있다.

우선순위 큐(Priority Queue) 는 검색에 특화된 트리처럼 임의의 값을 가진 원소를 검색할 수 있는 기능은 필요 없고 우선순위가 가장 높은 원소를 반환하고 삭제할 수 있으면 된다.

이러한 우선순위 큐는 배열, 링크드 리스트, 이진 탐색 트리등을 활용해서 구현할 수 있지만 Heap이 제일 효율적이다.

힙은 이진탐색트리인 바이너리 서치트리와는 다르게 값의 중복을 허용한다.
또한 바이너리 서치트리에서는 왼쪽 오른쪽을 기준으로 큰 값과 작은 값에 대한 제약이 있었다면 힙은 좌우 노드 간에는 값의 제약이 없고 상하 관계에서만 값의 제약을 갖게 된다.

• 위 아래가 아닌 좌우 자식 노드 간에는 크기관계에 제약이 없다.

흔히 Heap 이라고 말하면 정확히는 ‘Binary heap’을 가리킨다.

• 모든 부모 노드가 자식 노드보다 크거나 같은 값
• 완전 이진트리로 최대값, 최소값의 조회 및 추출을 효율적으로 수행할 수 있는 데이터 구조다.
• 최대 힙
  • 
  • 모든 노드의 값이 자식 노드의 값보다 크거나 같은 Heap
  • 가장 큰 원소가 루트 노드에 위치
• 최소 힙
  • 
  • 모든 노드의 값이 자식 노드의 값보다 작거나 같은 Heap
  • 가장 작은 우너소가 루트에 위치

완전 이진 트리

완전 이진 트리란 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨에서는 노드들을 왼쪽부터 차례대로 채워져 있는 이진 트리를 말한다.

Heap 배열로 표현하기

Heapify

• 힙의 재구조화
• 데이터 추가/삭제 후에도 힙의 속성을 유지하도록 해야함

데이터 삽입

• 완전 이진 트리의 형태를 유지해야 하므로 우선 leaf 노드에 삽입
• 힙의 조건을 만족하는지 계속 확인
• 힙의 조건을 만족할 때까지 부모노드와의 값을 바꿔주는 연산을 계속함

데이터 삭제

• 마찬가지로 루트노드가 제거 되면서 완전이진트리를 유지하기 위해 리프노드의 값을 루트노드로 올린다.
• 그 다음 힘의 조건이 완성될 때 까지 자식노드와 위치를 바꿔준다.

시간복잡도

• 힙의 최소,최대 값을 찾는 작업은 루트에 있는 값만 갖고 오면 되기 때문에 O(1)
• 삽입 삭제는 O(logN)
  • 데이터가 N개 있을 때 1/2 씩 인덱스를 줄여나가며 자신의 위치를 찾기 때문에 logN