알고리즘 기초 6.힙정렬

힙정렬 만들기

힙을 이용한 데이터 정렬 기법이 바로 힙 정렬이다. 

힙을 알기 위해서는 이진 트리 기법을 알고 있어야 할 필요성이 있다.

이진 트리란 컴퓨터 안에서 데이터를 표현 할떄 데이터를 각 노드에 담은 뒤에 노드를 두개씩 이어 붙이는 구조를 뜻한다.

이진트리는 모든 노드의 자식 노드가 두개 이하인 노드다.

위의 구조를 이진 트리라고 한다 트리는 말그대로 가지를 뻗어 나가는 것 처럼 데이터가 서로 연결되어 있다는 것을 의미합니다.

완전 이진 트리는 위에서와 같이 루트노드 부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식노드로 차근차근 들어가는 순서의 노드 입니다. 반드시 왼쪽에서부터 들어갑니다..

힙은 최솟값이나 최댓값을 빠르게 찾기위한 기반인 완전 이진트리를 사용합니다

1. 배열에 넣듯이 순서대로 일단 값을 넣는다.

. 

c언어

#include <stdio.h>
 
int number = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
 
int main(void){
    for(int i=1;i<number;i++){
        int c =i;
        do{
            //힙을 만들어 준다  
            int root = (c-1)/2; //root는 부모 
            if(heap[root]<heap[c]){ //부모의 값이 루트보다 작으면 값을 바꾼다. 
                int temp = heap [root];
                heap[root] = heap[c];
                heap[c] = temp;
                
            }
            c = root; 
        } while(c!=0);
        
    }
    //크기를 줄여가며 반복적으로 힙을 구성
    for(int i=number-1; i>=0 ; i--){
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        int root = 0;
        int c = 1;
        do{
            c = 2 * root+1;
            //자식 중에 더 큰 값을 찾기
            if(heap[c] <heap[c+1]&& c<i-1){
                c++;
            } 
            //루트보다 자식이 더 크다면 교환
            if(heap[root] < heap[c] && c<i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            } 
            root = c;
        } while(c < i)
    } 
}

java

package basic;
 
public class HeapSort {
    static int number = 9;
    static int heap[]= {7,6,5,8,3,5,9,1,6};
    public static void main(String[] args) {
        //힙정렬 구성
        for(int i=1;i<number;i++) {
            int c=i;
            //힙정렬 구성하는 부분..
            do {
            int root=(c-1)/2;
            //자식값이 부모보다 크면
            if(heap[root] < heap[c]) {
                int temp    = heap[root]; //기존 부모값을 temp에 담아둔다
                heap[root]   =heap[c];  //기존 자식값을 부모값 
                heap[c] =temp;    //temp에 담아둔 기존 부모값을 자식에 보냄
            }
            c =root;
            }while(c!=0);
        }
        
        for(int i=number-1;i>=0;i--) {
            int temp = heap[0];  //가장 위에있는 값이 크기떄문에 위에있는 값과 교체한다
            heap[0]  = heap[i];
            heap[i]  = temp;
            int root = 0;
            int c     = 1;
            //바꾸고 난 뒤만큼 다시 위에서 부터 힙정렬..
            do{
                c = 2 * root+1;//자식값
                //자식중에 더 큰 값을 찾는다.
                if(c<i-1&&heap[c]<heap[c+1]) {
                    c++;
                }
                //그값이 부모보다 크면  교환한다
                if(c<i&&heap[root]<heap[c]) {
                    int temp1 = heap[root];
                    heap[root] = heap[c];
                    heap[c]    =  temp1;
                }
                root = c;
                
            }while(c<i);
        }
        
        for(int i=0;i<number-1;i++) {
            System.out.println(heap[i]);
        }
    }
}