[알고리즘]힙 정렬

Juju·2023년 4월 13일
0

▪ 최악의 경우 시간복잡도 O(nlog2n)
▪ sorts in place - 추가배열 불필요
▪ 이진힙(binary heap) 자료구조를 사용

바이너리 힙이란?

heap은

  1. complete binary tree 이면서
  2. heap property를 만족해야

max heap property:
부모는 자식보다 크거나 같다. ===> MAX HEAP

or

min heap property :
부모는 자식보다 작거나 같다. ===> MIN HEAP

complete binary tree란

계층적 관계를 표현하기 위한 조직도

full binary tree

모든 레벨에 노드들이 꽉 차있는 형태

complete binary tree

마지막 레벨을 제외하면 완전히 꽉 차있고,
마지막 레벨에는 가장 오른쪽 부터 연속된 몇 개의 노드가 비어있을 수 있다

제일 꼭대기의 노드를 root 라고 한다.

트리와 이진트리의 정확한 개념은 다음 장에서...

heap sort 를 하려면 max heap을 사용하는것이 더 간단하다.

힙은 일차원 배열로 표현가능 : A[1...n] ===> n은 노드개수
▪ 루트 노드 A[1].
▪ A[i] 의 부모 = A[i/2]
▪ A[i] 의 왼쪽 자식 = A[2i]
▪ A[i] 의 오른쪽 자식 = A[2i+1]

기본연산 : Max - heapify

1.트리의 전체 모양은 complete binary 왼쪽의 subtree 그 자체로 heap 이고


루트노드가 heap property를 만족하지 못하고 있다.
이 상황에서 전체트리를 heap으로 바꿔주는 일을 하는게 max - heapify 이다.

유일하게 root node 만이 max-properity를 만족하지 않고 있다. root가 자기 자식보다 작음. root를 밑으로 내려보내고 밑에 있는것들 중 하나가 위로 올라와야 할 것이다.

  1. root 자식 노드에서 큰값을 선택한다. 16이 4보다 크기 때문에 바꾼다.

  2. 반댓쪽 상황을 본다면 16보다 15가 더 작다. 새로운 부모가 나보다 더 큰값이다.

  3. 4와 16이 자리를 바꾸더라도 문제가 없다.
    왼쪽 트리만 신경을 쓰면 된다.

  4. 4라는 값이 왼쪽 밑의 트리에서 조건충족이 되지 않아 문제이다.

  5. 처음과 동일한 상황이기 때문에, 4 밑의 노드에서 더 큰 것과 비교해서쓴다.

4가 leafnode까지 내려온다면 비교할 것이 없기 때문에 문제가 되지 않는다.

  1. heapify를 종료하게된다.

rootnode가 자식노드와 비교하여 더 큰것이 위로 가고
자신이 두 자식이 나보다 작아지거나
내가 leafnode까지 내려온다면 종료하게 된다.

heapiry는 본질적으로 recursive 한 성능을 띄고 있다.

MAX-HEAPIFY : interative version

MAX_HEAPIFY(A, i){
    if there is no childe of A[i]
        return;
    k <- index of the biggest child of i;
    if A[i] >= A[k]		//자식보다 부모가 더 크다면,
        return;
    exchange A[i] and A[k];	//노드를 바꾼다.
    MAX-HEAPIFY(A,k);
}

	//root 노드에 대한 heapify는 max-heapify(1)을 호출하면 된다

MAX_HEAPIFY(A,i){
    while A[i] has a child do
    k <- index of the biggest child of i;
    if A[i] >= A[k]
        return;
    exchange A[i] and A[k];
    i = k;
    end.
}

heap 에서 자식이 한명밖에 없는경우도 있다.
더큰값을 k라고 한다.

profile
짤막한 기록들..

0개의 댓글