자바스크립트로 구현한 Max Heap

자바스크립트로 구현한 Max Heap

 

힙(heap)은

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된

완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)다.

 

힙에는 두가지 종류가 있으며,

부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙',

부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

출처 : https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

 

자바스크립트로 구현한 Max Heap

class MaxHeap{
    constructor(){
        this.arr = [];
    }
    parent(index){
        return Math.floor((index-1)/2);
    }
    leftChild(index){
        return (index*2)+1;
    }
    rightChild(index){
        return (index*2)+2;
    }
    isLeaf(index){ // if index is a node that has no children, return true
        return (
            index >= Math.floor(this.arr.length / 2) && index <= (this.arr.length - 1)
        )
    }
    swap(index1, index2){
        [this.arr[index2], this.arr[index1]] = [this.arr[index1], this.arr[index2]];
    }
    add(element){
        this.arr.push(element); // add element to the end of heap
        this.heapifyUp(this.arr.length -1);
    }
    heapifyUp(index){
        let currentIndex = index;
        let parentIndex = this.parent(currentIndex);
        while(currentIndex > 0 && this.arr[currentIndex] > this.arr[parentIndex]){
            this.swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = this.parent(parentIndex);
        }
    }
    extractMax() { // remove and return max element
        if (this.arr.length < 1) return 'heap is empty';
    
        // get max and last element
        const max = this.arr[0];
        const end = this.arr.pop();
        // reassign first element to the last element
        this.arr[0] = end;
        // heapify down until element is back in its correct position
        this.heapifyDown(0);
    
        // return the max
        return max;
    }
    heapifyDown(index) {
        // if the node at index has children
        if (!this.isLeaf(index)) {
    
            // get indices of children
            let leftChildIndex = this.leftChild(index),
                rightChildIndex = this.rightChild(index),
    
                // start out largest index at parent index
                largestIndex = index;
    
            // if the left child > parent
            if (this.arr[leftChildIndex] > this.arr[largestIndex]) {
                // reassign largest index to left child index
                largestIndex = leftChildIndex;
            }
    
            // if the right child > element at largest index (either parent or left child)
            if (this.arr[rightChildIndex] >= this.arr[largestIndex]) {
                // reassign largest index to right child index
                largestIndex = rightChildIndex;
            }
    
            // if the largest index is not the parent index
            if (largestIndex !== index) {
                // swap
                this.swap(index, largestIndex);
                // recursively move down the heap
                this.heapifyDown(largestIndex);
            }
        }
    }
    buildHeap(array) {
        this.arr = array;
        // since leaves start at floor(nodes / 2) index, we work from the leaves up the heap
        for(let i = Math.floor(this.arr.length / 2); i >= 0; i--){
            this.heapifyDown(i);
        }
    }
    peek() {
        return this.arr[0];
    }
    print() {
        let i = 0;
        while (!this.isLeaf(i)) {
            console.log("PARENT:", this.arr[i]);
            console.log("LEFT CHILD:", this.arr[this.leftChild(i)]);
            console.log("RIGHT CHILD:", this.arr[this.rightChild(i)]);
            i++;
        }      
    }
}