공부/자료구조

[자료구조] Heap힙

knhoo 2024. 5. 16. 16:04
728x90

Selection / Insertions Sort의 문제점

  • 1단계 : 입력 set에서 큐 구축
  • 2단계 : 우선순위 큐 구축
  • Selection sort: Phase 1은 빠르지만 Phase 2는 매우 느리다.
  • Insertion sort: Phase 1은 매우 느리지만 Phase 2는 빠르다.

How can we balance the running times of the two phases?:

  • 효율적인 우선순위 큐의 구현은 heap이라는 데이터 구조를 사용

Heap Data Structures

Heap(힙): 이진 트리 T는 관계적 속성과 구조적 속성을 만

  1. 힙 순서 속성(Heap-order Property): 힙 T에서 루트가 아닌 모든 노드 v에 대해, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.
  2. 완전 이진 트리 속성(Complete binary tree property): 높이 h를 가진 힙 T에서
    • T의 레벨 0부터 h-1까지의 각 레벨은 가능한 최대 노드 수를 갖습니다. (레벨 i는 2^i개의 노드를 가집니다, 0 ≤ i ≤ h-1)
    • 레벨 h에서, 모든 내부 노드는 외부 노드의 왼쪽에 있으며, 최대 하나의 자식을 가진 노드가 있다. 이 자식은 왼쪽 자식이어야 함.
  • 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드

Height of a Heap

정리: 키 n개를 저장하는 힙은 높이 O(log n)

증명: 완전 이진 트리 속성complete binary tree

  • 키 n개를 저장하는 힙의 높이를 h라고 둔다.
  • i = 0부터 h - 1까지의 각 깊이에는 2^i개의 키가 있고, h 깊이에는 적어도 하나의 키가 존
  • 따라서, n ≥ 1 + 2 + 4 + ... + 2^(h-1) + 1
  • 따라서, n ≥ 2^h, 즉 h ≤ log n

힙과 우선순위 큐

  • 힙을 사용하여 우선순위 큐 구현
  • 각 내부 노드에는 (key, element)저장
  • 마지막 노드의 위치를 추적(루트 노드 포함)

Insertion into a Heap 힙 삽입

  1. 삽입 노드 z를 찾는다. (새로운 마지막 노드)
  2. z에 k를 저장
  3. 힙 순서 속성 heap - order property 복원

Upheap

  • 새로운 키 k가 insert 된 이후에는 heap order에 위배될 수 있다.
  • upheap 알고리즘은 삽입 노드로부터 위쪽 경로를 따라 k를 교환
  • k가 루트에 도달하거나, parent의 키가 k보다 작거나 같은 노드에 도달할 때까지 실행
  • 힙의 높이 = O(log n) ⇒ upheap 실행 시간 : O(log n)

Removal from a Heap 힙에서 제거

  1. 루트의 키를 마지막 노드 w로 대체
  2. w를 제거
  3. 힙 order 복원

Downheap

  • 루트 키를 k로 대체하면 힙 order이 깨질 수 있다.
  • downheap 알고리즘은 아래쪽 경로를 따라 키 k를 교환
  • k가 리프 노드에 도달하거나, child의 키가 k보다 크거나 같은 노드에 도달할 때까지 실행
  • 힙의 높이 = O(log n) ⇒ upheap 실행 시간 : O(log n)

Updating the Last Node

  • 삽입 노드는 O(log n)노드의 경로를 탐색하여 찾을 수 있다.
  1. Last node가 left-child인 경우 : Sibling이 insertion 위치
  2. Last node가 Right-child인 경우 :
    1. left-child 노드를 만날 때 까지 이동 → Right-child(Sibling)으로 이동→리프노드를 만날 때까지 Left로 이동
    2. 루트를 만날 때까지 이동→ 리프 노드를 만날 때까지 Left로 이동 → Leaf노드가 insertion 위치

Bottom-up Heap Construction

O(n)

Heap-Sort

  • 공간 : O(n)
  • insert , removeMin : O(logn)
  • size, isEmpty, min : O(1)
  • 힙 정렬 : O(nlogn)
  • 삽입 정렬이나 선택 정렬보다 빠르다

In-Place Heap Sort

  • 시퀀스는 배열을 통해 구현된다고 가정
  • 힙 정렬을 가속화, 공간 요구 사항을 상수 배로 줄임
  • 시퀀스의 원소를 재배열
  • 힙의 원소는 S의 왼쪽 부분(i-1)에 저장
  • 정렬되지 않은 원소는 오른쪽 부분(i부터 n까지)에 저장
  • S의 첫 i개의 원소는 힙의 벡터 표현을 제공한다.
  • empty heap에서 시작해서 경계를 한칸씩 오른쪽으로 이동
  • i단계에서는 i의 원소를 추가하여 힙을 확장

Phase 1 : Heap 만들기

  • 빈 heap에서 시작하여 힙과 시퀀스의 경계를 오른쪽으로 이동한다.

Phase 2 : Heap 정렬

  • 빈 시퀀스에서 시작하여 힙과 시퀀스의 경계를 왼쪽으로 이동한다.

Merging Two Heaps

  • 두 개의 Heap과 키 k가 주어진다.
  • 루트 노드로 k를 갖고 두 개의 Heap을 sub Tree로 갖는 새 Heap을 생성
  • heap - order 특성을 복원하기 위해 downHeap을 사용
    •  
728x90