컴퓨터알고리즘#7

LeeMir, 31 March 2021

힙과 힙정렬

내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리
- 힙순서(최소 힙의 경우)
  - 루트를 제외한 모든 내부노드 v에 대해, key(v) >= key(parent(v))
  - 자식 노드가 항상 부모 노드보다 크거나 같음(중복 허용)
- 완전 이진 트리
  - 왼쪽부터 채우는 이진 트리
  - 트리에서 깊이가 i인 노드는 2^(i)개 존재
  - 깊이 h-1에서 항상 내부 노드가 외부 노드의 왼쪽에 있음
    - 외부 노드 : null인 leaf 노드
힙을 사용하여 우선순위 큐 구현 가능
- 마지막 노드의 위치를 관리
배열을 이용해 구현한 힙과 리스트를 이용해 구현한 힙은 대부분의 경우 시간 복잡도가 동일하고, 마지막 노드를 찾는 데에 있어서 배열의 경우 O(1), 리스트는 순회를 해야해서 O(log n)임
삽입 메쏘드
- 가장 첫 외부 노드에 삽입 후, 확장(자식 노드로 두 외부 노드를 연결)
- upHeap 수행
  - 힙 순서가 꼬였을 수 있으므로 마지막 노드(삽입한 노드)로부터 루트까지 부모와 자식을 비교하면서 정리함
삭제 메쏘드
- 루트에 마지막 노드의 key를 집어 넣음, 원래 루트 값은 반환할 값
- 마지막 노드는 삭제(외부노드화)
- downHeap 수행
  - 루트부터 자식과 비교해나가면서 제자리를 찾게함
  - 왼쪽 자식 오른쪽 자식 중, 값이 더 작은 자식과 비교