알고리즘 공부 [힙]

힙에 대한 알고리즘 공부를 해보자.

힙은 heap이라고 해서, 다른 의미로 생각할 수 있지만, 쉽게 말하면 단순히 완전 이진 탐색 트리이다.

완전 이진 트리라고 생각하면 된다.

특징으로는 아래와 같다.

- 하위의 자식 노드는 무조건 2개가 있다.

- 왼쪽이 작거나 오른쪽이 크거나 할 것없이, 단순히 부모가 자식보다 큰게 다이다.

- 0의 index는 비워두고 1부터 계산한다. 해당 이유는, 부모는 자식노드 /2 , 오른쪽 은 /2+1 이런식으로 간단하게 구하기 위해서이다.

- 최대힙, 최소힙이 존재하여, 데이터를 탐색하는용도 보다 최대값 최소값을 빠르게 찾기 위해서 사용한다.

 

우선 힙과, 힙에 데이터를 넣는 메소드를 재구현 해보자

데이터를 넣을때, 항상 넣은 데이터와 부모의 데이터를 비교해서, 두개의 swap이 필요한지를 체크해서 처리해주도록 하자

해당 체크로직은 insert 구문에 넣기로하고, 해당 바꿀 필요가없다면 종료하는 로직을 구현하였다.

import java.util.*;

public class Main
{
public static void main(String[] args) {
    myHeap heap =  new myHeap();
    heap.insertData(10);
    heap.insertData(3);
    heap.insertData(14);
    heap.insertData(12);
    heap.printList();
}
}
class myHeap{
    ArrayList<Integer> heapList = new ArrayList<>();
    
    void insertData(int data)
    {
        //처음 넣는 경우
        if(this.heapList.size() ==0)
        {
            this.heapList.add(null);
            this.heapList.add(data);
        }
        else{
        this.heapList.add(data);
        }
    
    int currIndex = heapList.size() -1;
    while(true){
    if(currIndex == 1)
        break;
    //마지막으로 들어간 노드가, 부모의노드 보다 큰경우
    if(heapList.get(currIndex) > heapList.get(currIndex/2))
    {
        Collections.swap(heapList,currIndex,currIndex/2);
        currIndex = currIndex/2;
    }
    else
        break;
    }
        
    }
    void printList(){
    System.out.print(heapList.get(1));   
    }
    
}

 

맘대로 넣어도 insert의 swap 부분에서 해당 두개의 요소를 swap 하기 때문에

해당 swap 처리가 잘 되어 14, 즉 최대 힙의 최대 값이 잘 출력되는 것을 확인할수 있다.

 

만약에 해당 힙에서 pop을 하게된다면...?

1. root의 값과, 맨마지막 요소를 swap 한다.

해당 swap 후에 swap한 요소의 하위요소들이 해당 요소보다 크다면, 해당 요소와 하위요소를 하나씩 swap해주면서 다시 위치를 잡아준다.

 

 

import java.util.*;

public class Main
{
public static void main(String[] args) {
Heap heap = new Heap(3);
heap.insertHeap(4);
heap.insertHeap(5);
heap.insertHeap(6);
heap.showAllList();
}
}
class Heap{
    public ArrayList<Integer> heapArray =null;
    public Heap(Integer data){
        this.heapArray = new ArrayList<Integer>();
        this.heapArray.add(null);
        this.heapArray.add(data);
    }
    public boolean insertHeap(int data)
    {
        Integer insert_index,parent_idx;
        
        heapArray.add(data);
        insert_index = heapArray.size()-1;
        //move_up, 한개씩 부모_index를 체크를 해서, 더 크다면 true로 리턴한다.
        //ArrayList로 add를 하게 되면, index는 자동으로 size() -1 번째로 들어간다.
        while(move_up(insert_index))
        {
            parent_idx = insert_index /2;
            Collections.swap(heapArray,insert_index,parent_idx);
            insert_index = parent_idx;
        }
        return true;
        
    }
    
    public boolean move_up(Integer index)
    {
        if(index < 2)
            return false;
        else{
        if(heapArray.get(index) > heapArray.get(index/2))
            {
                return true;
            }
        }
        return false;
        
    }
    public void showAllList()
    {
        for(Integer x : heapArray)
        {
            System.out.println(x);
        }
    }
}

 

해당으로 우선 insert와 print함수를 다시 한번 복습해봤다.

저 순으로 add를 해도, 결국 print 는 아래와 같이 된다.

 

import java.util.*;

public class Main
{
public static void main(String[] args) {
Heap heap = new Heap(3);
heap.insertHeap(4);
heap.insertHeap(5);
heap.insertHeap(6);
heap.showAllList();
heap.pop();
heap.showAllList();


}
}
class Heap{
    public ArrayList<Integer> heapArray =null;
    public Heap(Integer data){
        this.heapArray = new ArrayList<Integer>();
        this.heapArray.add(null);
        this.heapArray.add(data);
    }
    public boolean insertHeap(int data)
    {
        Integer insert_index,parent_idx;
        
        heapArray.add(data);
        insert_index = heapArray.size()-1;
        //move_up, 한개씩 부모_index를 체크를 해서, 더 크다면 true로 리턴한다.
        //ArrayList로 add를 하게 되면, index는 자동으로 size() -1 번째로 들어간다.
        while(move_up(insert_index))
        {
            parent_idx = insert_index /2;
            Collections.swap(heapArray,insert_index,parent_idx);
            insert_index = parent_idx;
        }
        return true;
        
    }
    
    public boolean move_up(Integer index)
    {
        if(index < 2)
            return false;
        else{
        if(heapArray.get(index) < heapArray.get(index/2))
            {
                return true;
            }
        }
        return false;
        
    }
    public Integer pop()
    {
        Integer returned_data,popped_idx,left_child_popped_idx,right_child_popped_idx;
        if(heapArray.size() <=1)
        {
            return null;
        }
        //어떤것을 삭제했는지를 return 하기 위해
        returned_data = this.heapArray.get(1);
        //1번째 get한 요소(최소힙이라면 최소값 , 최대 힙이라면 최대값이 삭제 된다.)
        //1번째 요소에, 제일 마지막요소를 우선 set해준다.
        this.heapArray.set(1,heapArray.get(heapArray.size() -1));
        //1번째로 고정으로 오기 때문에 우선 넣어준다.
        popped_idx = 1;
        //하나씩 노드를 내려가면서 계산한다. 해당 계산후에 필요한 작업들을 해준다.
        while(move_down(popped_idx))
        {
            left_child_popped_idx = popped_idx * 2;
            right_child_popped_idx = popped_idx * 2+1;
            //힙은 완전 2진트리이기 때문에 둘다있거나, 왼쪽만 있는 경우만 가능
            //해당 케이스는 왼쪽만 존재하는 경우
            if(right_child_popped_idx >= this.heapArray.size())
            {
                //만약 힙의 값이 아래왼쪽 자식 노드보다 크다면? 최소힙이기때문에 바꿔준다.
                if(heapArray.get(popped_idx) > heapArray.get(left_child_popped_idx))
                    {
                        Collections.swap(heapArray,popped_idx,left_child_popped_idx);
                        popped_idx = left_child_popped_idx;
                    }
               
            }
            
            //둘다 존재하는 경우
            else{
                //오른쪽이 더 크다면,오른쪽과 비교해서 판단, 최소힙이기 때문에, 오른쪽 보다 크다면, 굳이 판단 가치가 없다.
                if(heapArray.get(right_child_popped_idx) > heapArray.get(left_child_popped_idx))
                {
                    if(heapArray.get(popped_idx)  > heapArray.get(right_child_popped_idx) )
                    {
                        Collections.swap(heapArray,popped_idx,right_child_popped_idx);
                        popped_idx = right_child_popped_idx;
                    }
                }
                //오른쪽이 더 크다면,오른쪽과 비교해서 판단, 최소힙이기 때문에, 오른쪽 보다 크다면, 굳이 판단 가치가 없다.
                if(heapArray.get(right_child_popped_idx) < heapArray.get(left_child_popped_idx))
                {
                    if(heapArray.get(popped_idx)  > heapArray.get(left_child_popped_idx) )
                    {
                        Collections.swap(heapArray,popped_idx,right_child_popped_idx);
                        popped_idx = left_child_popped_idx;
                    }
                }
                
            }
            
        }
        
        return returned_data;
    }
    //해당 함수는 아래로 갈수있는지 없는지를 체크하는 함수이다.
    //아래로 내려가서 바꿀께 있다면 true, 아니면 false
    public boolean move_down(Integer popped_idx)
    {
        Integer right_child_popped_idx,left_child_popped_idx;
        right_child_popped_idx = popped_idx * 2 + 1;
        left_child_popped_idx = popped_idx * 2;
        //case1. 왼쪽도 없을때(둘다 없을때)
        if(left_child_popped_idx >= heapArray.size())
        {
            return false;
        }
        //오른쪽 만 없을때
        else if(right_child_popped_idx >= heapArray.size())
        {
            //해당 오른쪽만 없을때는, 왼쪽이 현재 비교대상보다, 작은지 체크(바꿔줘야 하는지 체크)
            if(heapArray.get(left_child_popped_idx) < heapArray.get(popped_idx))
                return true;
            else
                return false;
        }
        //전부 존재하는 경우는, left와 right 를 비교, 
        else
        {
            if (this.heapArray.get(left_child_popped_idx) < this.heapArray.get(right_child_popped_idx)) {
                if (this.heapArray.get(popped_idx) > this.heapArray.get(right_child_popped_idx)) {
                    return true;
                } else {
                    return false;
                }
            } else {
                if (this.heapArray.get(popped_idx) > this.heapArray.get(left_child_popped_idx)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        
    }
    
    public void showAllList()
    {
        for(Integer x : heapArray)
        {
            System.out.println(x);
        }
    }
    
    
}

 

다음은 pop을 하는경우이다.

 

쉽게 생각하면, 크게 생각하면 이렇게 구조를 짜면된다.

 

1. 아래로 내려가서 바꿀께 있는지를 체크하는 boolean함수를 작성

2. 1번의 함수를 바탕으로 while문을 돈다.그리고 해당 하는 케이스를 체크해서, 변경 및 작업을 해준다.

3. 왼쪽노드만 있거나, 둘다 있거나, 없거나,  이 3가지 케이스를 생각해서 각각의 케이스 별로 처리를 해준다.

 

끗