Java - 정렬 알고리즘 - 5 (힙 정렬)

◎힙 정렬

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방식, 최대 힙을 구성하면 내림차순 정렬을, 최소 힙을 구성하면 오름차순 정렬을 할 수 있다.

---

◎힙 정렬의 특징

 

1. 비교 정렬(comparison sort)

 힙 정렬은 데이터를 비교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)이 아님

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다

 

3.  불안정 정렬(unstable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되지 않는다.

---

※자료구조 heap에 대하여! (heap 정렬의 이해를 위해서는 자료구조 heap을 무조건 알아야 한다.)

& 자바에서 구현된 heap, priority queue에 대하여!

https://kkwong-guin.tistory.com/58

Java - heap(힙) & Priority Queue(우선 순위 큐)

---

◎힙 정렬의 동작

1. 최소 힙을 구현하고, 최소 힙에 모든 원소를 넣는다. (heap에 원소를 넣으면 알아서 반정렬 상태가 된다)

2. root노드(가장 작은 값)을 계속해서 삭제하면서 정렬한다. (최소 heap의 root노드는 언제나 가장 작은 값이다)

 

출처: https://t1.daumcdn.net/cfile/tistory/0335233E51A98A111A

heap 자료구조의 특성상 넣으면 반정렬상태(부모 노드의 값이 언제나 자식 노드의 값보다 작은 상태)를 유지하기 때문에, heap 내부의 동작과정 외에는 특별한 추가 정렬 동작과정없이 정렬이 구현된다.

---

◎힙 정렬의 구현

1. PriorityQueue를 사용한 힙 정렬

package SortAlgorithm;

import java.util.Arrays;
import java.util.PriorityQueue;

public class sort {
	
    private void priorityQueue_heapsort(int[] numarr) {
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
		for(int i = 0; i<numarr.length; i++) {
			priorityQueue.add(numarr[i]); //priority queue에 각 원소 넣기
		}
		
		int i = 0;
		while(!priorityQueue.isEmpty()) {
			numarr[i] = priorityQueue.poll();
			//우선순위 순서대로(숫자가 작은 순서대로) 원소 반환
			//원래의 배열에 복사
			i++;
		}
		
		print(numarr, "우선순위 큐를 사용한 힙 정렬");
	}
    // 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.priorityQueue_heapsort(numarr);

	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
우선순위 큐를 사용한 힙 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

 

2. 구현한 heap 클래스를 사용한 힙 정렬

 

<heap 구현>

heap.java

 

package SortAlgorithm;

import java.util.ArrayList;
import java.util.Collections;

public class heap {

	private ArrayList<Integer> heaparray;
	
	heap(){
		 heaparray = new ArrayList<>();
	}	
	
	//부모 노드 인덱스 찾기
	private int getparents(int idx) { 
		
		if(idx==0){ //루트 노드의 부모는 없음
			return -1;
		}
		
		int index =idx+1;
		// 부모 노드 = (자식 노드+1) /2 -1
		return index/2 -1;
	}
	
	//왼쪽 자식 노드 인덱스 찾기
	private int getleftchild(int idx) {
		
		
		int index =idx+1;
		//왼쪽 자식 =  (부모+1)* 2 -1
		if(index*2 -1>= heaparray.size()-1) {
			return -1; //자식이 없으면 -1 반환
		}else {
			return index*2 -1;
		}
	}
	
	//오른쪽 자식 노드 인덱스 찾기
	private int getrightchild(int idx) {
		
		int index =idx+1;
		//오른쪽 자식 =  (부모+1)* 2
		if(index*2 >= heaparray.size()-1) {
			return -1; //자식이 없으면 -1 반환
		}else {
			return index*2;
		}
	}
	
	//heap 삽입
	void add(int num) {
		heaparray.add(num); //우선 맨끝에 삽입
		
		int me = heaparray.size()-1;
		int parents = this.getparents(me);
		
		//heap 다시 정렬
		//부모가 없을 때까지 반복	
		while(parents != -1 ) {		
			if(heaparray.get(me)<heaparray.get(parents)) { //부모보다 내가 작으면 부모와 나를 바꿈
				Collections.swap(heaparray, me, parents);
			}else {
				break;
			}
			
			me = parents;
			parents = this.getparents(me);
		}
	}
	
	//heap 삭제
	int delete() {
		//맨 앞의 원소를 맨뒤의 원소와 바꾸고 삭제
		Collections.swap(heaparray, 0, heaparray.size()-1);
		int delete = heaparray.remove(heaparray.size()-1); //삭제된 원소는 가장 작은 값임
		
		int me = 0;
		int leftchild = this.getleftchild(me);
		int rightchild = this.getrightchild(me);
		
		/*자식이 leftchild부터 채워지므로, leftchild가 없는 경우에는 rightchild도 없지만
		 * rightchild가 없는 경우에도 leftchild는 있을 수 있다
		 */
		
		//heap 다시 정렬
		//leftchild가 없을 경우 (모든 자식이 없을 경우)에만 종료
		while(leftchild != -1) {
			// rightchild가 있고, 내가 자식보다 크고, rightchild가 자식들 중에 가장 작은 값일 경우에만 
			// rightchild와 me 교환
			if(rightchild != -1 && heaparray.get(me) >heaparray.get(rightchild) 
					&& heaparray.get(leftchild) > heaparray.get(rightchild)){
				Collections.swap(heaparray, me, rightchild);
				me = rightchild;
			}
			// 내가 자식보다 크고, leftchild가 자식들중에 가장 작은 값인 경우에만
			// leftchild와 me 교환
			else if(heaparray.get(me) >heaparray.get(leftchild)) {
				
				Collections.swap(heaparray, me, leftchild);
				me = leftchild;
			}else {
				break;
			}
			
			leftchild = this.getleftchild(me);
			rightchild = this.getrightchild(me);
			
		}
		
		return delete;
	}
	
	//isEmpty
	boolean isEmpty() {
		if(heaparray.size()==0) {
			return true;
		}else {
			return false;
		}
		
	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
우선순위 큐를 사용한 힙 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎힙 정렬 개선

 

위에서 구현한 힙 정렬은 원래 주어진 숫자 배열 외에 Priority Queue나 Heap class 가 필요하므로, 추가적인 공간을 사용하여 정렬을 한다. 추가적인 공간을 사용하므로 제자리 정렬(in-place sort)이 아니고, 공간복잡도도 O(1)보다 높다.

하지만, 배열 안에 heap구조를 정의하고 그 heap을 통해 정렬을 한다면 추가적인 공간을 사용하지 않고 공간복잡도 O(1)로 힙 정렬을 구현할 수 있다. 이를 제자리 힙 정렬(in-place heap sort)이라 한다.

 

① 제자리 힙 정렬(in-place heap sort)

제자리 힙 정렬의 동작:

 

제자리 힙 정렬의 동작은 크게 2가지로 나누어진다.

1. 비어있는 힙으로부터 출발, 힙과 리스트의 경계 idx를 증가시키며 모든 원소가 힙에 들어갈때까지 최대 힙을 확장

출처:https://youngminieo1005.tistory.com/31

힙과 리스트의 경계 idx를 ref_point라 하면,

1단계의 ref_point는 0이므로, index가 0인 원소만 최대 힙에 들어가 있다.

2단계의 ref_point는 1이므로, index가 0~1인 원소가 최대 힙에 들어가 있다.

...

6단계의 ref_point는 5이므로 index가 0~5인 원소가 최대 힙에 들어가 있다.

 

※최대힙은

- 부모 노드 index = (자식 노드 index+1) /2 -1

- 왼쪽 자식 index=  (부모 노드 index+1)* 2 -1

- 오른쪽 자식 index=  (부모 노드 index+1)* 2

- 부모 노드의 value > 자식노드의 value

의 규칙을 지키며 이루어져 있다.

 

2. 비어있는 리스트로부터 출발, 힙과 리스트의 경계 idx를 감소시키며 모든 원소가 리스트에 들어갈때까지 힙의 최대 원소를 삭제

 

출처: https://youngminieo1005.tistory.com/31

힙과 리스트의 경계 idx를 ref_point라 하면,

n단계의 ref_point는 5이므로, 최대 힙에서 최대값을 하나 빼서 index 5에 넣는다.

n-1 단계의 ref_point는 4이므로, 최대 힙에서 최대값을 하나 빼서 index 4에 넣는다.

...

최대 힙에서 최대값을 빼서 ref_point에 넣는 과정을 리스트에 모든 원소가 채워질때까지 반복한다.

 

 

제자리 힙 정렬(in-place heap sort) 구현

package SortAlgorithm;

public class sort {

	//제자리 힙 정렬(in-place heap sort) -1
	private void in_place_heapsort(int[] numarr) {
		for(int i = 1; i<numarr.length-1; i++) {
			in_place_heapsort_add(i,numarr);
		}
		
		for(int i = numarr.length-1; i>0 ; i--) {
			in_place_heapsort_delete(i,numarr);
		}
		
		print(numarr, "제자리 힙 정렬");
	}
	
	//제자리 힙 정렬(in-place heap sort) -2 (부모 idx, 자식 idx 찾기)
	private int in_place_heapsort_find(int type, int idx, int ref_point) {
		// type 0: 부모찾기, type 1: 왼쪽 자식 찾기, type 3: 오른쪽 자식찾기
		switch (type) {
        case 0:
        	if(idx==0){ //루트 노드의 부모는 없음
    			return -1;
    		}
    		
    		// 부모 노드 = (자식 노드+1) /2 -1
    		return (idx+1)/2 -1;
    		
    		/*
    		 * ref_point는 배열 안에서 정의된 heap의 마지막 idx +1
    		 * 그러므로 leftchild나 rightchild가 ref_point와 같거나 크면 heap의 범위를 넘어갔다고 생각해야함
    		 */
    		
    		
        case 1: 
    		//왼쪽 자식 =  (부모+1)* 2 -1
    		if((idx+1)*2 -1>= ref_point) {
    			return -1; //자식이 없으면 -1 반환
    		}else {
    			return (idx+1)*2 -1;
    		}
        case 2:  
    		//오른쪽 자식 =  (부모+1)* 2
    		if((idx+1)*2 >= ref_point) {
    			return -1; //자식이 없으면 -1 반환
    		}else {
    			return (idx+1)*2;
    		}
		}
		return -1;
		
	}
	
	//제자리 힙 정렬(in-place heap sort) -3 (배열 안에서 정의된 heap에 원소 넣기)	
	private void in_place_heapsort_add(int ref_point, int[] numarr ) {
		
		int me =ref_point;
		int parents = this.in_place_heapsort_find(0,me,ref_point);
		
		//heap 다시 정렬
		//부모가 없을 때까지 반복	
		while(parents != -1 ) {		
			if(numarr[me]>numarr[parents]) { //부모보다 내가 작으면 부모와 나를 바꿈
				swap(numarr, me, parents);
			}else {
				break;
			}
			
			me = parents;
			parents = this.in_place_heapsort_find(0,me,ref_point);
		}
		
	}
	
	//제자리 힙 정렬(in-place heap sort) -4 (배열 안에서 정의된 heap에서 원소 빼기)	
	private void in_place_heapsort_delete(int ref_point, int[] numarr ) {
		
		swap(numarr, ref_point, 0);
		
		int me  = 0;
		int leftchild = this.in_place_heapsort_find(1,me,ref_point);
		int rightchild = this.in_place_heapsort_find(2,me,ref_point);
		
		while(leftchild != -1) {
			// rightchild가 있고, 내가 자식보다 크고, rightchild가 자식들 중에 가장 작은 값일 경우에만 
			// rightchild와 me 교환
			if(rightchild != -1 && numarr[me] <numarr[rightchild] 
					&& numarr[leftchild]  < numarr[rightchild]){
				swap(numarr, me, rightchild);
				me = rightchild;
			}
			// 내가 자식보다 크고, leftchild가 자식들중에 가장 작은 값인 경우에만
			// leftchild와 me 교환
			else if(numarr[me] <numarr[leftchild]) {
				
				swap(numarr, me, leftchild);
				me = leftchild;
			}else {
				break;
			}
			
			leftchild = this.in_place_heapsort_find(1,me,ref_point);
			rightchild = this.in_place_heapsort_find(2,me,ref_point);
			
		}
	}
	
	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.in_place_heapsort(numarr);

	}
 }

 

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
제자리 힙 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

 

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

 

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm