[자료구조] 힙(Heap) 자료구조란 ?

1) 힙(Heap) 이란

특성

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

💡우선순위 큐(Priority Queue)

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

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

💡 완전 이진트리    

    1) 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
    2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다

• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태(느슨한 정렬 상태)
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
    간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 힙 트리에서는 중복된 값을 허용 (이진 탐색 트리에서는 중복된 값을 허용하지 않음)
  

💡반정렬 상태

반정렬 상태라는 것은, 트리 구조를 배열에 저장한 것이므로 배열로만 보았을 때는 완전히 정렬된 상태로 보이지는 않는다.

2) 종류

힙의 종류

1. 최대 힙(max heap)
   부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2. 최소 힙(min heap)
   부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

3) 힙 구현

• 이진 트리이기 때문에 당연히 부모와 자식 노드가 발생함
• 힙의 경우엔 보통의 완전 이진 트리와는 다르게 반정렬 상태(느슨한 정렬 상태)를 유지
  • 이는 최대힙이라면 큰 값이 부모 노드쪽에, 최소힙이라면 작은 값이 부모 노드 쪽에 배치되는 것만 유지하고 왼쪽 자식과 오른쪽 자식은 부모 노드보다 작은 값을 유지하기만 하면 됨
• 힙을 저장하는 표준적인 자료구조는 배열
• 구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용되지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음  (ex 루트 노드(1)의 오른쪽 노드 번호는 항상 3)

배열의 첫 원소는 사용하지 않으므로 부모와 자식 간 다음의 관계가 성립하며 완전 이진 트리의 일종이기 때문에 Binaray Search tree에서의 부모-자식 간 관계와 유사

왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2

출처:   https://ipwag.tistory.com/86

힙 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 새로운 노드를 부모 노드들과 교환한다.

출처 :   https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

힙 삭제

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
3. 힙을 재구성

출처 :   https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

 

4) 시간 복잡도

operation	time
Insertion	O(logn)
Deletion	O(logn)

 

참고자료

https://velog.io/@yanghl98/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Heap%ED%9E%99-%EA%B0%9C%EB%85%90-%EC%A2%85%EB%A5%98-%ED%99%9C%EC%9A%A9-%EC%98%88%EC%8B%9C-%EA%B5%AC%ED%98%84

[자료구조] Heap(힙) - 개념, 종류, 활용 예시, 구현

https://velog.io/@longroadhome/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JS%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-HEAP

[자료구조] JS로 구현하는 HEAP

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

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