코테/자료구조

힙 (Heap)

EnoughTT 2023. 8. 23. 14:27

힙 (Heap)

힙 (Heap) : 최대값과 최소값을 바르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)

 

힙 (Heap) 사용 이유

  • 배열로 최소/최대를 찾으려면 O(n) 으로 걸림
  • 힙 (Heap) 으로 최소/최대를 찾으면 O(logn) 으로 걸림
  • 우선순위 큐와 같이 최소/최대값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 활용됨

 

구조

  • 최소값을 구하는 힙 (최소 힙, Min Heap) 과 최대값을 구하는 힙 (최대 힙, Max Heap) 으로 분류
  • 힙은 아래 조건을 가지고 있는 자료구조
    • 최대 힙 경우 각 노드의 값이 자식 노드가 가진 값보다 크거나 같음
    • 최소 힙 경우 각 노드의 값이 자식 노드가 가진 값보다 크거나 작음
    • 완전 이진 트리 형태

 

힙 데이터 삽입 - 기본

힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 하단부 노드부터 채워지는 형태로 삽입

 

힙 데이터 삽입 - 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap)

먼저 삽입된 데이터는 완전 이진 트리 구조에 맞춰서 최하단부 왼쪽 노드부터 채워짐

부모 노드보다 값이 큰 경우 부모 노드와 위치를 바꿔주는 작업을 반복 (swap)

Binary Heap (Priority Queue) - VisuAlgo

힙 데이터 삽입 - 데이터 삭제 (Max Heap)

보통은 최상단 노드를 삭제하는 것이 일반적

  • 힙의 용도는 최소/최대를 root에 넣고 바로 꺼내 쓸 수 있도록 하는 것

상단 데이터 삭제 시, 가장 최하단부 왼족에 위치한 노드 (일반적으로는 가장 마지막에 추가한 노드)를 root 노드로 이동

root 노드값이 자식노드보다 작을 경우, root노드의 자식노드 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복 (swap)

Binary Heap (Priority Queue) - VisuAlgo

 

힙 구현

일반적으로 힙 구현 시 배열을 활용함

배열은 0번부터 시작이지만, root 노드 인덱스 번호를 1로 지정하면 구현이 조금 더 수월함

  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

힙 insert - 1

// ArrayList 활용
import java.util.ArrayList;

public class Heap {
    public ArrayList<Integer> heapList = null;
    
    public Heap (Integer data) {
        heapList = new ArrayList<>();
        
        heapList.add(null);    // 인덱스 0은 null
        heapList.add(data);    // 인덱스 1은 data
    }
}

 

힙 insert - 2

import java.util.ArrayList;

public class Heap {
    public ArrayList<Integer> heapList = null;
    
    public Heap (Integer data) {
        heapList = new ArrayList<>();
        
        heapList.add(null);  
        heapList.add(data);  
    }
    
    
    /*
    * insert
    * 인덱스 번호는 1번부터
    */
    public boolean insert(Integer data) {
        if(heapList == null) {
            heapList = new ArrayList<>();
            
            heapList.add(null);
            heapList.add(data);
            
        } else {
            heapList.add(data);
        }
        return true;
    }
}

 

힙 insert - 3

  • data > parent node = data, parent node swap
  • 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 때까지 반복

Collections.swap()

swap (스왑) 이란, 두 데이터의 위치를 맞바꾸는 것을 의미함

하나의 배열 안에 있는 두 데이터의 위치를 서로 맞바꾸고 싶을 때 사용 가능

swap 함수를 별도로 구현할 수도 있지만, JAVA 에서는 Collections 패키지에서 swap() 메서드를 제공해주고 있음

Collections.swap(List list, int a, int b)

  • list : 스왑할 데이터들이 들어 있는 배열 변수
  • a : 스왑할 데이터 인덱스 번호
  • b : 스왑할 데이터 인덱스 번호
import java.util.ArrayList;

public class Heap {
    public ArrayList<Integer> heapList = null;
    
    public Heap (Integer data) {
        heapList = new ArrayList<>();
        
        heapList.add(null);  
        heapList.add(data);  
    }
    
    
    /*
    * move
    */
    public boolean move_up(Integer insert_idx) {
       if(insert_idx <= 1) {
           return false;
       }
       
       Integer parent_idx = insert_idx / 2;
       if(this.heapList.get(insert_idx) > this.heapList.get(parent_idx)) {
           return true;
           
       } else {
           return false;
       }
    }
    
    
    /*
    * insert
    * 인덱스 번호는 1번부터
    */
    public boolean insert(Integer data) {
        if(heapList == null) {
            heapList = new ArrayList<>();
            
            heapList.add(null);
            heapList.add(data);
            return true;
        }
        
        this.heapList.add(data);
        inserted_idx = this.heapList.size() - 1;
        
        while(this.move_up(inserted_idx)) {
            parent_idx = inserted_idx / 2;
            
            // swap
            Collection.swap(this.heapList, inserted_idx, parent_idx);
            inserted_idx = parent_idx;
        }
        return true;
    }
}


Heap heap = new Heap(15);
heap.insert(10);
heap.insert(8);
heap.insert(5);
heap.insert(4);
heap.insert(20);

System.out.println(heapTest.heapArray);    // null, 20, 10, 15, 5, 4, 8

 

힙 delete - 1

보통 root 노드를 삭제하는게 일반적

import java.util.ArrayList;

public class Heap {
    public ArrayList<Integer> heapList = null;
    
    public Heap (Integer data) {
        heapList = new ArrayList<>();
        
        heapList.add(null);  
        heapList.add(data);  
    }
    
    
    /*
    * move
    */
    public boolean move_up(Integer insert_idx) {
       if(insert_idx <= 1) {
           return false;
       }
       
       Integer parent_idx = insert_idx / 2;
       if(this.heapList.get(insert_idx) > this.heapList.get(parent_idx)) {
           return true;
           
       } else {
           return false;
       }
    }
    
    
    /*
    * insert
    * 인덱스 번호는 1번부터
    */
    public boolean insert(Integer data) {
        if(heapList == null) {
            heapList = new ArrayList<>();
            
            heapList.add(null);
            heapList.add(data);
            return true;
        }
        
        this.heapList.add(data);
        inserted_idx = this.heapList.size() - 1;
        
        while(this.move_up(inserted_idx)) {
            parent_idx = inserted_idx / 2;
            
            // swap
            Collection.swap(this.heapList, inserted_idx, parent_idx);
            inserted_idx = parent_idx;
        }
        return true;
    }
    
    
    /*
    * pop
    */
    public Integer pop() {
        if(this.heapList == null) {
            return null;
        }
        return this.heapList.get(1);
    }
}

 

힙 delete - 2

상단 데이터 삭제 시, 가장 마지막에 추가한 노드를 root 노드로 이동

root 노드의 값이 자식 노드보다 작을 경우, root 노드의 자식 노드 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복 (swap)

import java.util.ArrayList;

public class Heap {
    public ArrayList<Integer> heapList = null;
    
    public Heap (Integer data) {
        heapList = new ArrayList<>();
        
        heapList.add(null);  
        heapList.add(data);  
    }
    
    
    /*
    * move
    */
    public boolean move_up(Integer insert_idx) {
       if(insert_idx <= 1) {
           return false;
       }
       
       Integer parent_idx = insert_idx / 2;
       if(this.heapList.get(insert_idx) > this.heapList.get(parent_idx)) {
           return true;
           
       } else {
           return false;
       }
    }
    
    
    /*
    * insert
    * 인덱스 번호는 1번부터
    */
    public boolean insert(Integer data) {
        if(heapList == null) {
            heapList = new ArrayList<>();
            
            heapList.add(null);
            heapList.add(data);
            return true;
        }
        
        this.heapList.add(data);
        inserted_idx = this.heapList.size() - 1;
        
        while(this.move_up(inserted_idx)) {
            parent_idx = inserted_idx / 2;
            
            // swap
            Collection.swap(this.heapList, inserted_idx, parent_idx);
            inserted_idx = parent_idx;
        }
        return true;
    }
    
    
    /*
    * pop
    */
    public Integer pop() {
        Integer return_data, pop_idx, left_child_pop_idx, right_child_pop_idx;
        
        if(this.heapList.size() <= 1) {
            return null;
        }
        
        return_data = this.heapList.get(1);
        this.heapList.set(1, this.heapList.get(this.heapList.size() - 1));
        this.heapList.remove(this.heapList.size() - 1);
        pop_idx = 1;
        
        while(this.move_down(pop_idx)) {
            left_child_pop_idx = pop_idx * 2;
            right_child_pop_idx = pop_idx * 2 + 1;
            
            if(right_child_pop_idx >= this.heapList.size()) {
               if(this.heapList.get(pop_idx) < this.heapList.get(left_child_pop_idx)) {
                  Collections.swap(this.heapList, pop_idx, left_child_pop_idx);
                  pop_idx = left_child_pop_idx;
               }
               
            } else {
                if(this.heapList.get(pop_idx) < this.heapList.get(right_child_pop_idx)) {
                  Collections.swap(this.heapList, pop_idx, right_child_pop_idx);
                  pop_idx = right_child_pop_idx;
               }
            }
        }
        return returned_data;
    }
    
    
    /*
    * move_down
    */
    public boolean move_down(Integer pop_idx) {
       Integer left_child_pop_idx, right_child_pop_idx;
       
       left_child_pop_idx = pop_idx * 2;
       right_child_pop_idx = pop_idx * 2 + 1;
       
       // 자식 노드가 하나도 없을 경우
       if(left_child_pop_idx >= this.heapList.size()) {
           return false;
       
       // 오른쪽 자식 노드만 없을 경우
       } else if(right_child_pop_idx >= this.heapList.size()) {
          if(this.heapList.get(popped_idx) < this.heapList.get(left_child_pop_idx)) {
             return true;
             
          } else {
             return false;
          }
          
       // 왼쪽/오른쪽 자식 노드가 모두 있을 경우
       } else {
          if(this.heapList.get(left_child_pop_idx) > this.heapList.get(right_child_pop_idx)) {
              if(this.heapList.get(popped_idx) < this.heapList.get(left_child_pop_idx)) {
                  return true;
                  
              } else {
                  return false;
              }
              
          } else {
              if(this.heapList.get(popped_idx) < this.heapList.get(right_child_pop_idx)) {
                  return true;
                  
              } else {
                  return false;
              }
          }
       }
    }
}

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스

저작자표시

'코테 > 자료구조' 카테고리의 다른 글

트리와 이진 탐색 트리 - 2  (0) 2023.08.18
트리와 이진 탐색 트리 - 1  (0) 2023.08.16
해쉬 테이블 (HashTable)  (0) 2023.08.15
링크드 리스트 (Linked List) - 2  (0) 2023.08.10
링크드 리스트 (Linked List) - 1  (0) 2023.08.10

'코테/자료구조'의 다른글

  • 현재글힙 (Heap)

관련글

티스토리툴바