2. 힙과 힙정렬

🔍힙이란?

 내부노드에 키를 저장하며 두가지 속성을 만족하는 이진트리

• 힙 순서 루트를 제외한 모든 내부노드 v에 대해 key(V) ≥ key(parent(v))를 만족
• 완전이진트리를 만족
  (힙의 높이 h일때 i = 0,….h-1에 대해 깊이 i인 노드가 2^i개 존재 내부노드들은 외부노드들의 왼쪽에 존재)

힙의 마지막 노드: 깊이 h-1의 가장 오른쪽 내부노드

힙의 높이 : n개의 키를 저장한 힙의 높이는 O(log n)이다.

🔍힙과 우선순위 큐

힙을 사용하여 우선순위 큐를 구현

전체: 적정 이진트리로 구현(모든 내부 노드가 2개의 자식을 가져야함

마지막 노드위치를 관리

그림 표기: 내부 노드 내에 간단히 키만 표시(내부 값은 생략하여 그린다.)

🔍삽입 연산(최소힙)

삽입연산(최소힙) 이미지

1. 위처럼 먼저 마지막 노드를 찾는다.
   • 마지막 노드에서 삽입한 후 마지막 노드가 될 노드를 찾는 방법(advenceLast())
     1. 현재 노드가 오른쪽 자식인 동안 부모노드로 이동
     2. 현재노드가 왼쪽 자식이면 형제노드로 이동(같은 높이의 노드로 이동하는 방법은 위 부모노드를 건너서)
     3. 현재 노드가 내부 노드이면 왼쪽자식으로 이동
     4. 위의 알고리즘으로 마지막 노드가 될 위치를 찾을 수 있다.
2. 이후 노드를 내부노드로 확장 시킨다.(하나짜리 노드를 아래 더미노드 둘 가진 노드로 확장)
3. 이후 힙 순서 속성에 맞도로 복구해야한다( 그림에선 위로 갈수록 낮은 숫자)
4. upheap알고리즘으로 상향경로를 따라가며 부모의 키가 더 크면 교환, 작거나 같으면 정지(O(logn)의 시간(높이만큼 걸림))

최소힙 삽입 알고리즘

 

🔍삭제 연산(최소힙)

삭제연산 최소

1. 루트키를 삭제 후 리턴
2. 라스트노드를 복사하여 넣어줌.
3. 원래 라스트노드는 삭제, 아래 더미노드또한 삭제
   • 삭제한 후 다음 라스트노드를 찾는법(retreatLast)
     1. 현재 노드가 왼쪽 자식인 동안 부모노드로 이동
     2. 현재노드가 오른쪽 자식이면 형제노드로 이동(같은 높이의 노드로 이동하는 방법은 위 부모노드를 건너서)
     3. 현재 노드가 내부 노드이면 오른쪽 자식으로 이동
     4. 끝까지 내려가면 다음 라스트노드가됨
4. 이후 양옆중 작은 노드와 교환, 이걸 반복, 양옆이 모두 같거나 크면 정지

최소힙 삭제연산 알고리즘

🔍배열에 기초한 힙(순차힙)

n개의 키를 가진 힙의 크기를 n개 배열로 표현할 수 있다.

접근법

• 왼쪽자식은 첨자 2i에 존재
• 오른쪽 자식은 첨자 2i+1에 존재,
• 부모노드는 첨자 i/2에 존재한다

노드사이의 링크는 명시적으로 저장할 필요 없음 (어차피 위의 식으로 계산가능

외부노드들은 표현할 필요 없다.

첨자 0은 사용하지 않는다(접근을 위한 노드)

마지막 노드의 첨자는 항상 n

insertItem 은 첨자 n+1위치에 삽입, removeMin은 첨자 n의 노드를 삭제

배열으로 구현할 경우 위에서 사용했던 삽입 삭제에서 lastNode를 찾는 과정에 상수시간만 소요된다.

🔍힙정렬

n개의 원소로 이루어진 리스트를 O(n log n)시간에 정렬할 수 있다.

외부에 힙을 새로 만들어준 후 그 힙의 원소를 꺼내어주는 방식으로 정렬한다.

힙의 생성과정에서 속도가 느리며, 추가로 메모리도 잡아먹는다.

🔍 제자리 힙정렬이 가능할까?

정렬되어야 할 리스트가 배열로 주어졌을때 적용할 수 있다.

힙을 저장할때 리스트 L의 일부를 사용한다.

그러나 최소힙 대신 최대힙을 사용하여 구현한다.

제자리 힙정렬

Alg inPlaceHeapSort

1. buildheap(A) : 배열속에서 힙을 생성한다.
2. downheap(A): 힙안에서 만족할때까지 내려간다.

리스트의 1번째 인덱스~ i번째 인덱스까지의 왼쪽부분은 힙의 원소들을 저장하는데에 사용된다.

그리고 리스트의 i+1번부터 n까지의 오른쪽 부분은 리스트의 원소들을 저장하는데 사용된다.

phase 1(힙생성)

• 비어있는 힙으로부터 출발해 힙과 리스트의 경계를 왼쪽에서 오른쪽으로 한번에 한칸씩 이동
• 단계 i(i=1,…,n)에서, 첨자 i에 있는 원소를 힙에 추가함으로써 힙을 확장.

phase2(정렬)

• 비어 있는 리스트로부터 출발하여 힙과 리스트의 경계를 오른쪽에서 왼쪽으로 한번에 한칸씩 이동
• 단계 i(i=n…2)에서, 힙의 최대 원소를 삭제하여 리스트의 첨자 i에 저장하여 리스트를 확장.

제자리 힙정렬

phase 1과 phase2의 각 단계에서, 배열 가운데 힙에 쓰인 부분이 파란색 배열이 노란색일때.

한 노드씩 가상적으로 힙을 생성한다.

리스트가 최대힙이 됨.

이제 다시 리스트로 변환해줌

정렬중

배열상 1번에 있는 노드를 LastNode와 자리를 바꿈, 이후 순서를 다시 제자리로

이걸 반복해줌

위와 같은 방식으로 힙정렬 구현이 가능하다.