힙 정렬

'''힙 정렬'''(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.
힙 정렬은 1964년 J. W. J. 윌리엄스에 의해 발명되었다. 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다. 같은 해, R. W. 플로이드는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 트리정렬 알고리즘으로 이어나가게 한 것이다.
최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
# n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
# 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
# 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
# 2와 3을 반복한다.
=== 시간복잡도 ===
이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 개의 데이터 삭제 및 재구성 시간을 포함한다.
시간 복잡도는
따라서 힙 정렬은 일반적인 경우 의 시간복잡도를 가진다.
=== C ===
void downheap(int cur, int k)
{
  int left, right, p;
    while(cur = k && right >= k) break;
      p = cur;
      if (left = 0; i--){
    downheap(i,n);
  }
  //for(i=0;i 0; ){
    swap(&data0,&datak);
    //k--;
    downheap(0,k);
    k--;
  }
}
=== 자바 ===
public class Heap
{
	private int element; //element0 contains length
	private static final int ROOTLOC = 1;
	private static final int DEFAULT = 10;
	public Heap(int size) {
		if(size>DEFAULT) {element = new intsize+1; element0 = 0;}
		else {element = new intDEFAULT+1; element0 = 0;}
	}
	public void add(int newnum) {
		if(element.length  1 && elementlocmark/2 > elementlocmark) {
			swap(locmark/2, locmark);
			locmark /= 2;
		}
	}
	public void downheap() {
		int locmark = 1;
		while(locmark * 2 = elementlocmark) break;
				swap(locmark,small);
				locmark = small;
			}
			else {
			    if(elementlocmark * 2 >= elementlocmark) break;
				swap(locmark, locmark * 2);
				locmark *= 2;
			}
		}
	}
	public void swap(int a, int b) {
		int temp = elementa;
		elementa = elementb;
		elementb = temp;
	}
	public int smaller(int a, int b) {
		return elementa 
힙 정렬의 예시.
가장 작은 것부터 가장 큰 것까지 정렬하고 싶은 리스트 { 6, 5, 3, 1, 8, 7, 2, 4 }가 있다고 하면 정렬 예시는 다음과 같다.
 1. 힙 만들기
 힙 
 새로 추가된 요소 
 요소 교체
 null 
 6 
  
 6 
 5 
  
 6, 5 
 3 
  
 6, 5, 3 
 1 
  
 6, 5, 3, 1 
 8 
  
 6, '''5''', 3, 1, '''8 '''
   
 5, 8
 '''6''', '''8''', 3, 1, 5 
   
 6, 8
 8, 6, 3, 1, 5 
 7 
  
 8, 6, '''3''', 1, 5, '''7''' 
   
 3, 7
 8, 6, 7, 1, 5, 3 
 2 
   
 8, 6, 7, 1, 5, 3, 2 
 4 
  
 8, 6, 7, '''1''', 5, 3, 2, '''4''' 
   
 1, 4
 8, 6, 7, 4, 5, 3, 2, 1 
   
  
 2. 정렬
 힙 
 요소 교체 
 요소 삭제 
 요소 정렬
 '''8''', 6, 7, 4, 5, 3, 2, '''1''' 
 8, 1 
   
   
 1, 6, 7, 4, 5, 3, 2, '''8''' 
   
 8 
   
 '''1''', 6, '''7''', 4, 5, 3, 2 
 1, 7 
   
 8
 7, 6, '''1''', 4, 5, '''3''', 2 
 1, 3 
   
 8
 '''7''', 6, 3, 4, 5, 1, '''2''' 
 7, 2 
   
 8
 2, 6, 3, 4, 5, 1, '''7'''       
      
 7 
 8
 '''2''', '''6''', 3, 4, 5, 1 
 2, 6 
   
 7, 8
 6, '''2''', 3, 4, '''5''', 1 
 2, 5 
   
 7, 8
 '''6''', 5, 3, 4, 2, '''1''' 
 6, 1 
   
 7, 8
 1, 5, 3, 4, 2, '''6'''          
   
 6 
 7, 8
 '''1''', '''5''', 3, 4, 2 
 1, 5 
   
 6, 7, 8
 5, '''1''', 3, '''4''', 2 
 1, 4 
   
 6, 7, 8
 '''5''', 4, 3, 1, '''2''' 
 5, 2 
   
 6, 7, 8
 2, 4, 3, 1, '''5''' 
            
 5 
 6, 7, 8
 '''2''', '''4''', 3, 1 
 2, 4 
   
 5, 6, 7, 8
 '''4''', 2, 3, '''1''' 
 4, 1 
   
 5, 6, 7, 8
 1, 2, 3, '''4'''          
   
 4 
 5, 6, 7, 8
 '''1''', 2, '''3''' 
 1, 3 
   
 4, 5, 6, 7, 8
 '''3''', 2, '''1''' 
 3, 1 
   
 4, 5, 6, 7, 8
 1, 2, '''3'''          
   
 3 
 4, 5, 6, 7, 8
 '''1''', '''2''' 
 1, 2 
   
 3, 4, 5, 6, 7, 8
 '''2''', '''1''' 
 2, 1 
   
 3, 4, 5, 6, 7, 8
 1, '''2''' 
   
 2 
 3, 4, 5, 6, 7, 8
 '''1''' 
   
 1 
 2, 3, 4, 5, 6, 7, 8
      
   
   
 1, 2, 3, 4, 5, 6, 7, 8
* 
분류:정렬 알고리즘
분류:힙
분류:비교 정렬