패스트캠퍼스 챌린지 8일차

데이터 구조 : 힙(Heap)

1. 힙(Heap) 이란?

  - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

  • 완전 이진 트리 (Complete Binary Tree)

   - 노드를 삽입할 떄 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

2. 힙을  사용하는 이유

  - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸린다.

   => 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다.

  - 최대값 또는 최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현 등에 활용

 

 • 힙과 이진트리의 공통점

  - 모두 이진 트리 이다

 • 차이점

  - 힙은 데이터 삽입 시 무조건 왼쪽에서 부터 데이터를 넣어, 왼쪽 및 오른쪽 자식의 노드 값은 어느것이 큰지 모른다.

  - 이진 탐색 트리는 검색(탐색)을 위한 구조, 힙은 최대/최소 값을 검색을 위한 구조

 

3. 데이터 삽입

  - 데이터 삽입 시 무조건 왼쪽부터 채우며 완전 이진트리를 만족하며 노드를 채운다.

  - 추가된 노드의 데이터가 부모 노드의 데이터보다 클 경우 부모노드와 자식노드의 위치를 바꾸며 (swap) 이진트리를 

    만족시키며 트리를 완성한다.

 

4. 데이터 삭제  

  - 데이터 삭제 시에는 root 노드를 삭제한 후 가장 마지막 데이터를 root노드에 올린 후 swap 과정을 통하여 

    완전 이진트리의 형태로 만든다

 

힙 구현

  • 힙과 배열

  - 일반적으로 힙 구현시 배열 자료구조를 활용

  - 배열은 인덱스가 0부터 시작하지만, 힙 구현의 편의를 위해, root 인덱스 번호를 1로 지정하면 구현이 수월

   • 부모노드 인덱스 번호 = 자식 노드 인덱스번호 / 2 의 몫
   EX) child index = 5 => 5 / 2 => 2.5 몫 2 = parent index

   • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2

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

 

Heap 데이터 삽입 및 제거

힙 클래스 구현 

import java.util.ArrayList;

public class Heap{
  public ArrayList<Integer> heapArray = null;
  
  public Heap(Integer data){
    heapArray = new ArrayList<Integer>();
    
    heapArray.add(null); // 0번 index을 null로 바꿈
    heapArray.add(data);
  }
  
  public boolean insert(Integer data){
    Integer inserted_idx,parent_idx;
    
    if(heapArray == null){
      heapArray = new ArrayList<Integer>(); 
            
      heapArray.add(null);
      heapArray.add(data);
      return true;
    }
    
    this.heapArray.add(data);
    inserted_idx = this.heapArray.size() - 1; // 배열의 맨 마지막 인덱스
    
    // 데이터 Swap
    while(this.moveup(inserted_idx)){
      parent_idx = inserted_idx / 2;
      Collections.swap(this.heapArray,inserted_idx,parent_idx);
      inserted_idx = parent_idx;
    }   
    return true;
  }
  
  private booelan move_up(Integer inserted_idx){
    if(inserted_idx <= 1){ // root 노드
      return false;
    }
    Integer parent_idx = inserted_idx / 2;
    if(this.heapArray.get(inserted_idx) > this.heapArray.get(parent_idx)){
      return true;
    }else{
      return false;
    }
  }
  
  // 데이터 삭제
 public Integer pop() {
   Integer returned_data, popped_idx, left_child_popped_idx, right_child_popped_idx; 
        
   if(this.heapArray == null) {
     return null;
   }else {
     returned_data = this.heapArray.get(1);
     this.heapArray.set(1, this.heapArray.get(this.heapArray.size() - 1));
     this.heapArray.remove(this.heapArray.size() - 1);
     popped_idx = 1;
            
     while (this.move_down(popped_idx)) {
       left_child_popped_idx = popped_idx * 2;
       right_child_popped_idx = popped_idx * 2 + 1;

     // CASE2: 오른쪽 자식 노드만 없을 때
     if (right_child_popped_idx >= this.heapArray.size()) {
       if (this.heapArray.get(popped_idx) < this.heapArray.get(left_child_popped_idx)) {
         Collections.swap(this.heapArray, popped_idx, left_child_popped_idx);
         popped_idx = left_child_popped_idx;
       }
     // CASE3: 왼쪽/오른쪽 자식 노드가 모두 있을 때                    
     } 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(left_child_popped_idx)) {
           Collections.swap(this.heapArray, popped_idx, left_child_popped_idx);
           popped_idx = left_child_popped_idx;
         } 
       } else {
         if (this.heapArray.get(popped_idx) < this.heapArray.get(right_child_popped_idx)) {
           Collections.swap(this.heapArray, popped_idx, right_child_popped_idx);
           popped_idx = right_child_popped_idx;
         } 
       }
     }
   }
            
            return returned_data;
        }
    }
  
  public boolean move_down(Integer popped_idx){
    Integer left_child_popped_idx,right_child_popped_idx;
    left_child_popped_idx = popped_idx * 2;
    right_child_popped_idx = popped_idx * 2 + 1;
  
    // case 1 : 자식 노드가 하나도 없을 떄
    if(left_child_popped_idx >= this.heapArray.size()){
      return false;
    }else if(right_child_popped_idx >= this.heapArray.size()){ // case 2 : 으론쪽 자식 노드만 없을 때
      if(this.heapArray.get(popped_idx) < this.heapArray.get(left_child_popped_idx)){
        return true
      }else{
        return false;
      }
    }else { // CASE3: 왼쪽/오른쪽 자식 노드가 모두 있을 때
      if(this.heapArray.get(left_child_popped_idx) > this.heapArray.get(right_child_popped_idx)) {
        if(this.heapArray.get(popped_idx) < this.heapArray.get(left_child_popped_idx)) {
          return true;
        } else {
          return false;
        }
      } else {
        if(this.heapArray.get(popped_idx) < this.heapArray.get(right_child_popped_idx)) {
          return true;
        }else {
          return false;
          }
        }
     }
  }
  
}

 

 

8일차 인증

 

 

현재 8일차를 기준으로 자료구조 이론 챕터를 마무리 하였다

현재는 이해만 하고 실제 코드를 작성할떄 어려움이 있을듯 하지만 알고리즘을 풀어보면서 한번씩 복기 식으로 

되짚어 보게된다면 이해하면서 코드를 작성할 수 있을듯 하다

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]