[Algorithm] 정렬 Sort - Heap sort

Heap

• 힙의 조건
  • complete binary tree(완전 이진 트리)이며,
  • heap property(min heap 또는 max heap)를 만족
• 동일한 데이터를 가진 여러개의 힙이 존재 가능
• 힙에서 각 노드의 위치 H(1..n)
  • 루트 노드 : H(1)
  • H(i)의 부모 : H(i/2)
  • H(i)의 왼쪽 자식 : H(2i)
  • H(i)의 오른쪽 자식 : H(2i+1)
• 힙은 일차원 배열로 표현 가능 A[0..n]
  • 루트 노드 : A[0]
  • A[i]의 부모 : A[(i-1)/2]
  • A[i]의 왼쪽 자식 : A[2i]+1
  • A[i]의 오른쪽 자식 : A[2i]+2

---

Max Heapify (힙 정렬)

• 왼쪽과 오른쪽 자식 트리가 모두 max heap property를 만족하고, root만이 조건을 만족하지 않을 때, 이 트리를 힙으로 만드는 연산
• 루트에서 시작하여 두 자식 노드 중 더 값이 큰 노드와 위치를 변경해가며, 리프노드가 되거나 자식노드가 모두 자신보다 작아질 때까지 반복

구현

• recursive version

maxHeapify(A, i) { //A는 배열로 표현된 힙, i는 문제가 되는 루트 노드의 인덱스
  if there is no child of A[i] //리프 노드가 되었을 때
    return;
  k <- index of the biggest child of i; //k는 두 자식 중 값이 더 큰 노드
  if A[i] >= A[k] //루트 노드의 값이 자식 노드의 값보다 클 때
    return;
  exchange A[i] and A[k]; //값을 교환
  maxHeapify(A, k); //옮겨진 위치로 다시 함수 호출
}

• iterative version

maxHeapify(A, i) { //A는 배열로 표현된 힙, i는 문제가 되는 루트 노드
  while A[i] has a child do //자식 노드를 가지는 동안만 반복
    k <- index of the biggest child of i; //k는 두 자식 중 값이 더 큰 노드
    if A[i] >= A[k] 
      return;
    exchange A[i] and A[k]; //값을 교환
    i=k; //k를 새로운 i 값이라고 설정하고 다시 반복문 실행
  end.
}

실행 코드 

public class Sort_heapSort {
	static int size = 0; //데이터가 추가되어 있는 부분만큼의 배열의 길이
	private static void swap(int[] data, int a, int b) {
		int temp = data[a];
		data[a] = data[b];
		data[b] = temp;
	}
	
	private static void print(int[] data) {
		for(int i=0; i<data.length; i++) { //size보다 1 작을 때까지 출력
			System.out.print(data[i] + " ");
		} System.out.println("\n");
	}
	
	private static void buildMaxHeap(int[] data) {
		int length = data.length+1;
		for(int i = (length/2)-1; i>=0; i--) { //배열은 0부터 시작하므로 -1 수행
			maxHeapify(data,i);
		}	
	}

	private static void maxHeapify(int[] data, int i) { //data는 배열,i는 루트 노드의 인덱스
		int root = i;
		int length = data.length;
		int leftChild = (i*2)+1; //배열은 0부터 시작하므로 +1
		int rightChild = (i*2)+2; //배열은 0부터 시작하므로 +2
		
		//리프 노드까지 탐색을 끝냈을 때
		if(leftChild > length && rightChild > length)
			return;

		//leftChild가 존재하고. 루트 노드의 값보다 클 때
		if(leftChild<length && data[leftChild]>data[i])  //leftChild가 존재하고 루트 노드의 값보다 클 때
			root = leftChild; //루트에 leftChild의 인덱스 할당
		
		//rightChild가 존재하고, 루트 노드의 값보다 크거나 leftChild의 값보다도 클 때
		if (rightChild<length && data[root]<data[rightChild]) 
			root = rightChild; //루트에 rightChild의 인덱스 할당
		
		//기존 루트보다 큰 값의 자식이 있을 때
		if(root != i) {
			swap(data, i, root); //실제 노드의 값 교환
			maxHeapify(data, root); //변경된 루트로 다시 max heapify 진행 
		}
	}

	public static void main(String[] args) {
		int data[] = { 5, 2, 100, 7, 12, 42, 62, 52};
		buildMaxHeap(data); //max heap property를 만족하도록 정렬
		print(data); //max heap 출력
	}
}

 

---

Piroity Queue (우선순위 큐)

• 최대 우선순위 큐 (maximum priority queue)
  
  • INSERT(x) : 새로운 원소 x를 삽입
  • EXTRACT_MAX() : 최대값을 삭제하고 반환
• 최소 우선순위 큐 (minimum piority queue)
  • INSERT(x) : 새로운 원소 x를 삽입
  • EXTRACT_MIN() : 최소값을 삭제하고 반환

구현

• INSERT(x) : max heap에 새로운 값을 삽입

• pseucode

MAX-HEAP-INSERT(A, key) { //A는 배열로 표현한 힙, key는 새로 추가할 값
  heap_size = heap_size + 1; //힙 사이즈 1 추가
  A[heap_size] = key; //맨 마지막 인덱스에 key 추가
  i = heap_size; //추가한 노드의 인덱스
  while (i > 1 and A[PARENT(i)] < A[i]) { //루트 노드가 아니고, 부모 노드의 값보다 큰 동안
    exchange A[i] and A[PARENT(i)]; //위치 변경
    i = PARENT(i); //변경한 값의 인덱스를 다시 i로 설정
  }
}

 

• EXTRACT_MAX() : max heap에서 최대값을 삭제하고 반환하는 pseudocode
• max heap에서 최대값은 항상 루트 노드에 위치

• pseudocode

HEAP-EXTRACT-MAX(A){
   if heap-size[A] < 1 //예외 처리
     then error "heap underflow";
   max <- A[1]; //루트 노드를 최대값으로 설정
   A[1] <- A[heap-size[A]]; //배열의 마지막 값(힙의 마지막 노드)를 루트 노드로 옮김
   heap-size[A] <- heap-size[A] - 1 //힙의 마지막 노드를 삭제
   MAX-HEAPIFY(A, 1) //루트 노드에 대하여 max heapify 수행
   return max;
}

실행코드

public class Sort_heapSort {
	static int current = 0; //데이터가 추가되어 있는 부분만큼의 배열의 길이
	
	private static void swap(int[] data, int a, int b) {
		int temp = data[a];
		data[a] = data[b];
		data[b] = temp;
	}
	
	private static void print(int[] data) {
		for(int i=0; i<current; i++) { //current보다 1 작을 때까지 출력
			System.out.print(data[i] + " ");
		} System.out.println("\n");
	}
	
	private static void maxHeapify(int[] data, int i) { //data는 배열,i는 루트 노드의 인덱스
		int root = i;
		int length = current;
		int leftChild = (i*2)+1; //배열은 0부터 시작하므로 +1
		int rightChild = (i*2)+2; //배열은 0부터 시작하므로 +2
		
		System.out.println("i ->_>_. : " + i);
		System.out.println("leftchild : " + leftChild);
		System.out.println("rightchild : " + rightChild);
		
		//리프 노드까지 탐색을 끝냈을 때
		if(leftChild > length && rightChild > length)
			return;

		//leftChild가 존재하고. 루트 노드의 값보다 클 때
		if(leftChild<length && data[leftChild]>data[i])  //leftChild가 존재하고 루트 노드의 값보다 클 때
			root = leftChild; //루트에 leftChild의 인덱스 할당
		
		//rightChild가 존재하고, 루트 노드의 값보다 크거나 leftChild의 값보다도 클 때
		if (rightChild<length && data[root]<data[rightChild]) 
			root = rightChild; //루트에 rightChild의 인덱스 할당
		
		//기존 루트보다 큰 값의 자식이 있을 때
		if(root != i) {
			swap(data, i, root); //실제 노드의 값 교환
			print(data);
			maxHeapify(data, root); //변경된 루트로 다시 max heapify 진행 
		}
	}

	private static void maxHeapInsert(int[] data, int key) {
		data[current] = key; //배열의 마지막 인덱스에 key 값 추가
		int i = current++; //추가한 노드의 인덱스, 다음 연산을 위해 size 1 추가
		int parent = (i-1)/2;
		while(i>0 && data[parent]<data[i]) { //루트 노드가 아니고, 부모 노드의 값보다 큰 동안
			swap(data, i, parent); //값 교환
			i = (i-1)/2; //i와 parent의 값을 교환했으므로 인덱스도 parent의 인덱스로 할당
			parent = (i-1)/2; //인덱스 i값이 변화했으므로, 새로운 i의 parent 인덱스로 할당
		}
	}

	private static int maxHeapExtract(int[] data) { //최대값을 뽑아내는 함수
		if(current < 1)
			System.out.print("heap underflow");
		int max = data[0]; //루트 노드의 값이 최대값
		data[0] = data[--current]; //힙의 마지막 노드의 값을 루트 노드로 이동, 배열의 길이를 1씩 줄임
		maxHeapify(data, 0); //변경된 루트 노드에 대하여 max heapify 수행
		return max; //최대값 반환
	}
	
	public static void main(String[] args) {
		int[] data = new int[100];
		//heap에 데이터 추가
		maxHeapInsert(data, 4);
		maxHeapInsert(data, 1);
		maxHeapInsert(data, 13);
		maxHeapInsert(data, 2);
		maxHeapInsert(data, 16);
		maxHeapInsert(data, 9);
		maxHeapInsert(data, 10);
		maxHeapInsert(data, 14);
		maxHeapInsert(data, 8);
		maxHeapInsert(data, 77);
		print(data);
		
		maxHeapExtract(data);
		maxHeapInsert(data, 20);
		maxHeapExtract(data);
		print(data);
	}
}