[javascript] 우선순위 큐, heap (2)

heap 이란 ? 

heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. 

 

heap은 부모노드와 자식노드의 대소관계에 따라 최대힙(Max heap)과 최소힙(Min heap)으로 나뉜다. 

 

heap의 특징

 

• heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기
• heap은 트리내에서 중복된 값을 허용한다.
• heap은 느슨한 정렬(반 정렬) 상태를 가진다. 

반 정렬 이라는 의미는 자식노드가 부모의 노드보다 무조건 크거나 작다. 그러나 전체트리를 볼 때는 가장 아래에 있는 노드가 가장 작거나 큰 값은 아니라는 의미이다. 

 

Max heap 최대 힙

 

  

최대힙은 다음과 조건을 항상 만족한다. 자식노드 value >= 부모노드 value 

 

Min heap 최소 힙

최소힙은 다음과 같

55

은 조건을 항상 만족한다. 자식노드 value <= 부모노드  value

 

Heap의 사용이유

• 삽입시 O(log n) 의 시간 복잡도를 가진다.
• 삭제시 O(log n)의 시간 복잡도를 가진다. 

일반적인 연결리스트와 배열로 만들어 하던 삽입과 삭제는 O(n)혹은 O(1)이였는데 heap의 사용으로 적은 시간복잡도를 가지고 삽입과 삭제 가 균형적인 시간복잡도를 가지게 되었다 .

 

Heap의 사용 

heap 또한 이진탐색트리와 인덱스의 관계가 같다. 또한 배열로 heap을 구성할 수 있지만 연결리스트로도 만들 수 있다.

55

• 왼쪽 자식노드 인덱스 : 부모노드 인덱스 * 2  
• 오른쪽 자식노드 인덱스 : (부모노드 인덱스 * 2) + 1 
• 부모노드 인덱스 : 자식노드 / 2 소수점 버림 

삽입 구현

최대 힙을 구성하려면 완전이진트리에 맞게 자식노드의 왼쪽부터 채우고 오른쪽 노드를 삽입해야 한다. 그렇기에 가장 먼저 할일은 트리에 마지막 레벨에 삽입하고 순서에 맞게 삽입하고 해당 노드의 부모노드와 비교한 후 순위를 바꾸면 된다. 

 

 

 enqueue(item){
        this.size +=1;

        let i = this.size; // 마지막 노드를 가리킨다.
        while(this.array[Math.floor(i/2)] <= item && i != 1){
            this.array[i] = this.array[Math.floor(i/2)]
            i = Math.floor(i/2);
        }
        this.array[i] = item; 
        console.log(this.array);
    }

 

//설명은 위에 것이 제일 적당하지만 위 설명과 같이 똑같이 하면 temp 변수를 둬서 매번 스왑하는 연산을 한번 더 거쳐야 하기에 부모노드를 따라가면서 부모노드와 자식노드를 바꾸고 마지막에 해당하는 자리에 item을 삽입하게 했다. 

 

// 소수점 출력 때문에 5/2 가 2.5 가 되어 Math.floor()메서드를 사용해서 소수점아래로 전부 버림 하였다. 

 

완전 이진트리에 성격에 맞게 노드생성

 

18과 10 비교 후 부모노드와 자식노드 데이터 치환

 

18과 11 비교 후 부모노드와 자식노드 데이터 치환

18과 19 비교 후 18이 19보다 더 작으니 해당 노드에 삽입

 

삭제 구현

힙의 삭제는 가장 높은 곳에 있는 노드의 데이터를 지우고 맨 마지막에 삽입된 노드를 지워진 노드의 자리로 옮기고 삽입된 노드와 자식노드를 비교하며 부모노드가 자식 노드보다 작다면 서로를 치환 하며 맨 마지막 노드에 이르거나 부모노드가 자식노드보다 크다면 해당 반복을 중지하는 함수이다. 

 

dequeue(){
        let remove = this.array[1];
        let temp = this.array.pop();
        this.array[1] = temp; 
        this.size--;

        let parent = 1; 
        let childe = 2;
        
        while(childe <= this.size){
            // 두 자식중 큰 노드와 부모노드랑 비교 
            if(this.array[childe] < this.array[childe + 1] && childe < this.size){
                childe += 1; 
            }

            if(temp >= this.array[childe]) break; // 만약 자식 노드와 비교해서 크다면 해당 반복문 멈춤 
            this.array[parent] = this.array[childe]; 
            parent = childe;
            childe *=2;
        }
        this.array[parent] = temp;
        console.log(this.array);
        return remove;
    }

 

// 자식노드 왼쪽,오른쪽 중 max heap , min heap의 성질에 맞게 그 중 큰것 혹은 작은 것과 치환 하여야 한다. 

// size 프로퍼티는 array.length로 변환 가능하다. 

 

가장 우선순위가 높은 1번 노드데이터를 removed 에 할당한다.

기존 가장 높은 노드를 삭제하고 그 자리에 가장 늦게 생성된 노드를 넣는다. 

 

1번 노드의 자식들을 서로 비교해 둘 중 더 큰 노드와 치환한다.

2번 노드의 자식 노드를 서로 비교한 뒤 더 큰 노드와 부모노드와 치환한다.