힙정렬

힙이란?

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

힙의 종류

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

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

    

힙 구현하기

• 힙은 배열을 통해 쉽게 만들 수 있다.
• 구현의 용이성을 위해 0번째 인덱스는 사용하지 않는다.
  

  

• 힙에서 부모 노드와 자식 노드의 관계
  • 왼쪽 자식 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

힙 삽입 연산

1. 힙에 새로운 요소가 들어오면, 힙의 끝에 삽입한다.
2. 새로운 노드를 부모노드들과 비교 교환해서 힙의 성질은 만족시킨다.
   

   

   
   

   

힙 삭제 연산

1. 최대 힙에서 최대값(루트노드)를 삭제한다.
2. 삭제된 루트 노드에 마지막 노드를 넣는다.
3. 힙을 재구성한다
4. 
   

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