[정렬] 힙 정렬

[정렬] 힙 정렬

힙

힙정렬을 이해하기 전에 힙에 대한 이해가 필요하다. 힙을 이해하기 위해선 다음 포스트를 확인해보자.

https://ybdeveloper.tistory.com/132

힙 정렬이란?

Max Heap, Min Heap을 구성해 정렬하는 방법이다.

내림차순 정렬을 위해서는 Max Heap, 오름차순 정렬을 위해서는 Min Heap을 구성하면 된다.

즉, 데이터들을 Max Heap이나 Min Heap 형태로 유지한 채 루트 노드의 데이터를 뽑아내 정렬을 하는 방식이다.

힙 정렬 구현 (내림차순)

1. n개의 데이터에 대해 반복한다. O(n)

1-1. 배열에 데이터를 삽입하며 Max-Heap 특성을 만족하도록 조정한다. O(lgn)

2. Max-Heap에 데이터가 존재하지 않을 때 까지 데이터를 뽑아낸다. O(n)

힙 정렬 JAVA로 구현하기

public void insert(int n) { heap[idx] = n; int parent = idx/2; int child = idx; while(child >= 2 && heap[parent] < heap[child]) { SWAP(parent, child); child = parent; parent = child/2; } idx++; } public int delete() { int data = heap[1]; heap[1] = heap[idx--]; int parent = 1; int child = 2; while(child <= idx && heap[parent] < heap[child]) { SWAP(parent, child); parent = child; child = heap[heap[parent * 2] < heap[parent * 2 + 1] ? parent * 2 + 1 : parent * 2]; } return data; } public void SWAP(int idx1, int idx2) { int temp = heap[idx1]; heap[idx1] = heap[idx2]; heap[idx2] = temp; }

위 코드는 Max Heap을 구현한 코드이다. Max Heap은 데이터를 삽입하거나, 삭제해도 특성을 유지하고 최상단 루트 노드에는 가장 큰 값을 가진 노드가 위치하게 된다. 따라서 힙 정렬을 구현하기 위해서는 단순히 힙의 특성을 활용하여 가장 맨 위에 있는 루트 노드의 데이터를 가져와 출력 시켜주기만 하면 정렬된 데이터를 얻을 수 있다.

이를 구현한 코드는 아래와 같다.

public void sort() { int temp = heapSize; for(int i=0; i

힙정렬의 시간 복잡도

데이터 삽입

데이터를 삽입하는 작업은 최악의 경우 모든 Level의 노드에 대해 비교 연산을 진행해야 하므로 O(lgn)이다. 그런데 데이터 삽입 작업을 모든 데이터에 대해 반복하므로 O(n * lgn) 이라고 할 수 있다.

데이터 삭제

데이터를 삭제하는 작업은 최악, 최선 모두 O(1)의 시간 복잡도를 가지고 있다. 데이터 삭제 작업 또한 모든 데이터에 대해 반복하므로 O(n * 1) 이지만, 데이터가 무한대로 커진다면 O(n)은 O(n * lgn)에 비해 큰 영향을 주지 못하므로 생략이 가능하다.

따라서 힙 정렬의 시간 복잡도는 O(n * lgn)이다.

from http://ybdeveloper.tistory.com/135 by ccl(A) rewrite - 2021-11-11 00:26:48