자바스크립트로 자료구조 힙 구현하기

banhogu·2023년 6월 6일

프로젝트 기간 2023/05/26 ~ 2023/06/01

설계 목적 : 학부 자료구조 강의 과제 및 힙에 대한 이해

설계 요구사항

소스코드

const readline = require('readline');

// MinHeap class를 만들어 각 메소드 관리
class MinHeap {
    constructor() {
        this.heap = []; //a 메뉴 입력시 힙생성
    }

    // 
    swap(i, j) { //c,d 메뉴 입력시 두 인덱스 요소 스왑하는 기능
        const temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }

    // 하위 트리 힙
    heapify(i) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;

        if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
            smallest = left;
        }

        if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
            smallest = right;
        }

        if (smallest !== i) {
            this.swap(i, smallest);
            this.heapify(smallest);
        }
    }

    // d 메뉴 입력시 힙에 요소 삽입
    insert(key) {
        this.heap.push(key);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor((currentIndex - 1) / 2);

        while (
            currentIndex > 0 &&
            this.heap[currentIndex] < this.heap[parentIndex]
        ) {
            this.swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
    }

    // 힙에 가장 작은 값 제거
    removeMin() {
        if (this.heap.length === 0) { //힙 생성 안됐으므로 null리턴하여 종료
            return null;
        }

        if (this.heap.length === 1) { //요소 1개일시 그냥 바로 pop되게
            return this.heap.pop();
        }

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapify(0);
        return min;
    }

    // 임의요소 우선순위 변경
    changePriority(oldKey, newKey) {
        const index = this.heap.indexOf(oldKey);
        if (index === -1) {
            return false; // indexOf로 찾은값이 없을 때
        }

        this.heap[index] = newKey;

        const parentIndex = Math.floor((index - 1) / 2);
        if (index > 0 && this.heap[index] < this.heap[parentIndex]) {
            while (
                index > 0 &&
                this.heap[index] < this.heap[parentIndex]
            ) {
                this.swap(index, parentIndex);
                index = parentIndex;
                parentIndex = Math.floor((index - 1) / 2);
            }
        } else {
            this.heapify(index);
        }

        return true; // 
    }

    // 현재 힙 표시. console.log로 계속 반복 출력하다 보니 그냥 함수로 만들었습니다.
    displayHeap() {
        console.log("현재 힙 상태 ", this.heap);
    }
}

// prompt()가 안돼 reeadline으로 입력값을 받았습니다.
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let heap;

// 메인메뉴
function mainMenu() {
    console.log("=== 아래 메뉴 중 한개를 입력하세요 ===");
    console.log("a. 힙 만들기");
    console.log("b. 가장 낮은 값 지우기");
    console.log("c. 우선순위 변경");
    console.log("d. 힙에 요소 추가");
    console.log("e. 끝내기");

    rl.question("메뉴를 선택하세요 (a-e) 중 입력:", (option) => {
        option = option.toLowerCase();

        switch (option) {
            case "a":
                heap = new MinHeap();
                console.log("힙 만들기 완료.");
                heap.displayHeap();
                mainMenu();
                break;
            case "b":
                if (heap) {
                    const min = heap.removeMin();
                    console.log("제거된 가장 낮은 값 :", min);
                    heap.displayHeap();
                } else {
                    console.log("힙이 아직 안만들어졌습니다");
                }
                mainMenu();
                break;
            case "c":
                if (heap) {
                    rl.question("바꿀 이전 값 입력: ", (oldKey) => {
                        rl.question("새로운 값 입력: ", (newKey) => {
                            const isPriorityChanged = heap.changePriority(oldKey, newKey);
                            if (isPriorityChanged) {
                                console.log("키 변환 성공.");
                                heap.displayHeap();
                            } else {
                                console.log("힙에서 요소를 찾을수 없습니다.");
                            }
                            mainMenu();
                        });
                    });
                } else {
                    console.log("힙이 아직 안만들어졌습니다.");
                    mainMenu();
                }
                break;
            case "d":
                if (heap) {
                    rl.question("힙에 추가할 요소를 입력하세요 ", (element) => {
                        heap.insert(element);
                        console.log("힙에 요소가 추가되었습니다");
                        heap.displayHeap();
                        mainMenu();
                    });
                } else {
                    console.log("힙이 아직 안만들어졌습니다.");
                    mainMenu();
                }
                break;
            case "e":
                rl.close();
                return;
            default:
                console.log("다시 선택하세요");
                mainMenu();
                break;
        }
    });
}

// 시작
mainMenu();