[자료구조] 힙 (Heap)

 

 

 

손글씨로 패드에 정리하다가 블로그로 옮기는 자료구조..
전에 패드에 정리한건 천천히 옮겨두어야겠다

 

 

힙 : heap

완전 이진 트리의 일종
여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

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

 

❓ 완전 이진트리    

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

 

❓반정렬 상태  

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

 

 

힙(Heap) 규칙

큐에는 FIFO, 스택은 FILO의 규칙이 있듯  힙(Heap)에도 규칙 있다. 

Heap Rule : 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.

 

따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다. 

• 최댓값이 맨 위인 힙을 최대힙(max-heap), 최솟값이 맨 위인 힙을 최소힙(min-heap)이라고 한다.
• BST(이진 탐색 트리)와 다르다. 좌, 우 자식의 위치가 대소 관계를 반영하지 않는다. (층(level)으로 대소 관계를 구분한다.)
• 왼쪽 자식과 오른쪽 자식은 부모 노드보다 작은 값을 유지하기만 하면 된다.   
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
  
  

  

❓ 최대힙과 최소힙

  - 최대 힙(Max heap)
      부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
      key(ParentNode)>=key(ChildNode)

    - 최소 힙(Min heap)
      부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
      key(ParentNode)=<key(ChildNode)

힙 자료구조를 트리와 배열로 보기

Heap 자료구조 Tree 형태

Heap 자료구조 배열

  

배열 형태로 보면 1번 노드부터 10번 노드까지 Index에 순서대로 넣는 형태

트리 구조를 배열로 구현했으니 0번 Index는 사용하지 않는다. (편의상)

 

index찾기

트리 구조의 특성에 따른 것으로,

Index 값을 좌측 자식은 부모 노드의 x2,

우측 자식은 부모 노드의 x2 + 1로 설정하고

부모 노드는 자식 노드 아무 쪽에서든, 1/2을 곱해주면 바로 구할 수 있기 때문이다.

 

 

힙의 재정렬(Heapify) ,Big-O

Heapify 

Heapify는 힙을 고친다라는 의미로,

현재 삽입 혹은 삭제될 노드에 의해 전체 정렬 상태에 영향이 생길 경우 그 정렬을 다시 올바르게 진행하기 위한 절차를 의미한다.

 

삽입

원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다.

완전 이진트리의 최대 높이는 O(logN)이고, 반복하는 최대 횟수도 O(logN)이 된다.

 

삽입 시에는 가장 마지막 배열 위치에 값을 우선 넣고 진행하므로 상단으로 힙을 재정렬해야 한다.

https://hongjw1938.tistory.com/22

 

 

 

삭제(추출)

원소를 맨 위 넣어서 바닥까지 비교하면서 올린다.

완전 이진트리의 최대높이는 O(logN)이고, 반복하는 최대횟수도 O(logN)이된다. 

 

현재 최우선 순위의 데이터를 추출해냈다면 배열의 가장 마지막에 있는 데이터를 최우선 순위 위치로 가져다 놓는다.

그 다음 아래 방향으로 재정렬(Heapify)를 진행하면 된다.

 

https://hongjw1938.tistory.com/22

 

 

 

 

 

 

---

✔️ 참고

https://hongjw1938.tistory.com/22
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html   
https://algoroot.tistory.com/m/69
https://code-lab1.tistory.com/8
 https://velog.io/@jaenny/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99-%EC%B5%9C%EC%86%8C%ED%9E%99-%EC%B5%9C%EB%8C%80%ED%9E%99