21-03-14 자바스크립트로 하는 자료구조와 알고리즘(9)

16장 힙

힙은 O(1) 시간으로 가장 높은 항목이나 가장 낮은 항목을 반환하는 중요한 자료 구조
힙은 트리와 비슷한 자료 구조의 일종으로 최대 힙의 경우 부모가 자식보다 크고 최소 힙의 경우 부모가 자식보다 작다
힙은 자식에 대한 포인터를 갖는 대신에 배열을 사용해 자료를 저장함
배열을 사용하므로 인덱스를 통해 힙 노드의 자식 위치를 쉽게 계산할 수 있다
힙이 배열을 사용해 자료를 저장하기 때문에 인덱스는 각 항목의 차수/높이를 정의 한다
첫 번째 배열 항목을 루트로 설정하고 각 왼쪽 항목과 오른쪽 항목을 순서대로 채워 이진 힙을 만들 수 있다

최대 힙은 루트노드가 가장 높은 값을 갖고 최소 힙은 루트노드가 가장 낮은 값을 갖는다

class Heap {
    // 힙은 배열을 사용해 자료를 저장
    constructor () {
        this.items = [];
    }

    // 두 개의 인덱스에 위치한 값을 바꾸는 것도 인덱스 값으로 변경 가능함
    swap(idx1, idx2) {
        let temp = this.itmes[idx1];
        this.itmes[idx1] = this.items[idx2];
        this.items[idx2] = temp;
    } 

    parentIndex(idx) {
        return Math.floor((idx-1)/2);
    }

    leftChildIndex(idx) {
        return index * 2 + 1;
    }

    rightChildIndex(idx) {
        return idx * 2 + 2;
    }

    parent(idx) {
        return this.items[this.parentIndex(idx)];
    }

    leftChild(idx) {
        return this.items[this.leftChildIndex(idx)];
    }

    rightChild(idx) {
        return this.items[this.rightChildIndex(idx)];
    }

    peek(item) {
        return this.items[0];
    }

    size() {
        return this.items.length;
    }
}

예를들어 최소 힙 구조인 배열이 [2, 4, 23, 12, 13] 라면 부모 노드인 0번 인덱스 2가 부모가 될 것이고 1번 인덱스인 4는 왼쪽 자식이, 2번 인덱스인 23은 오른쪽 자식이 된다
항상 좌측이 먼저 채워지고 우측이 채워지므로 3번 인덱스는 1번 인덱스의 왼쪽 자식이 되고 4번 인덱스는 1번 인덱스의 오른쪽 자식이 된다
정리하면 자신의 인덱스가 N이라고 한다면 부모는 (N - 1)/2 의 인덱스를 가질 것이고(예를 들어 N = 3 일 때, 부모의 인덱스는 1), 왼쪽 자식은 (N * 2) + 1 의 인덱스를, 힙 배열이 순차적이라면 오른쪽 자식은 바로 옆에 붙어있어야 하므로 (N * 2) + 2 의 인덱스를 가질 것이다

항목을 추가하거나 삭제하더라도 힙의 구조가 유지되어야 한다

class MinHeap extends Heap{
    constructor () {
        super();
        this.items = [];
    }

    add(item) {
        this.items[this.items.length] = item;
        this.bubbleUp();
    }

    poll() {
        let item = this.items[0];
        this.items[0] = this.items[this.items.length - 1];
        this.items.pop();
        this.bubbleDown();
        return item;
    }

    bubbleDown() {
        let index = 0;
        while (this.leftChild(index) && this.leftChild(index) < this.items[index]) {
            let smallerIndex = this.leftChildIndex(index);
            if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex])
                smallerIndex = this.rightChildrenIndex(index);  
            this.swap(smallerIndex, index);
            index = smallerIndex;
        }
    }

    bubbleUp() {
        let index = this.items.length - 1;
        while(this.parent(index) && this.parent(index) > this.items[index]) {
            this.swap(this.parentIndeX(index), index);
            index = this.parentIndex(index);
        }
    }
}

최대 힙의 경우 최소 힙에서 구현한 bubbleDown과 bubbleUp 내 비교자 뿐이다

bubbleDown() {
    let index = 0;
    while (this.leftChild(index) && this.leftChild(index) > this.items[index]
            || this.rightChild(index) > this.items[index]) {
        let biggerIndex = this.leftChildIndex(index);
        if (this.rightChild(index) && this.rightChild(index) < this.items[biggerIndex])
            biggerIndex = this.rightChildrenIndex(index);  
        this.swap(biggerIndex, index);
        index = biggerIndex;
    }
}

bubbleUp() {
    let index = this.items.length - 1;
    while(this.parent(index) && this.parent(index) < this.items[index]) {
        this.swap(this.parentIndeX(index), index);
        index = this.parentIndex(index);
    }
}

힙 노드 인덱스 요약

노드	인덱스
자신	N
부모	(N - 1) / 2
왼쪽 자식	(N * 2) + 1
오른쪽 자식	(N * 2) + 2

힙은 삼투를 통해 자신의 구조를 유지한다(bubbleUp, bubbleDown)
이 삼투 과정이 있어 삭제와 삽입이 O(log2(n)) 시간에 가능해진다

일련의 숫자에서 중간 값을 찾기

/*
    하나의 최소 힙과 하나의 최대 힙을 만들면 중간 값을 얻는 데 O(1)시간이 걸림
*/

class MedianHeap {
    constructor() {
        this.minHeap = new MinHeap();
        this.maxHeap = new MaxHeap();
    }

    add(value) {
        if (value > this.median()) 
            this.minHeap.add(value);
        else 
            this.maxHeap.add(value);
        

        if (this.minHeap.size() - this.maxHeap.size() > 1) 
            this.maxHeap.add(this.minHeap.poll());
        
        if (this.maxHeap.size() - this.minHeap.size() > 1)
            this.minHeap.add(this.maxHeap.poll());
    }

    median() {
        if(this.minHeap.size() === 0 && this.maxHeap.size() === 0) 
            return Number.NEGATIVE_INFINITY;
        else if (this.minHeap.size() === this.maxHeap.size())
            return (this.minHeap.peek() + this.maxHeap.peek()) / 2;
        else if (this.minHeap.size() > this.maxHeap.size()) 
            return this.minHeap.peek();
        else 
            return this.maxHeap.peek();
    }
}

배열에서 K번째로 가장 작은/큰 값 찾기

let arr = [12, 3, 13, 4 ,2, 40, 23];
const getKthSmallestElement = (arr, k) => {
    let minH = new MinHeap();
    for (let i = 0, len = arr.length; i < len; i++) {
        minH.add(arr[i]);
    }
    
    for (let i = 1; i < k; i++) {
        minH.poll();
    }

    return minH.poll();
}

const getKthSmallestElement = (arr, k) => {
    let maxH = new MaxHeap();
    for (let i = 0, len = arr.length; i < len; i++) {
        maxH.add(arr[i]);
    }
    
    for (let i = 1; i < k; i++) {
        maxH.poll();
    }

    return maxH.poll();
}

17장 그래프

그래프를 사용하면 객체 간의 연결을 다양하게 나타낼 수 있다
그래프 기본 용어 및 개념

단어	뜻
정점	그래프를 형성하는 노드로 원으로 표기
간선	그래프에서 노드 간의 연결로 정점(원)사이의 선으로 표기
정점 차수	해당 점점에 연결된 간선의 개수
희소 그래프	정점들 간 가능한 연결 중 일부만 존재하는 경우
밀집 그래프	다양한 정점들 간에 연결이 많은 경우
순환 그래프	어떤 정점에서 출발해 해당 정점으로 다시 돌아오는 경로가 있는 지향성 그래프
가중치	간선에 대한 값으로 문맥에 따라 다양한 것을 나타냄(정점 간 거리 등)

무지향성 그래프는 간선 간에 방향이 없는 그래프로 노드 간 방향 없이 상호 연결을 뜻한다
인접 행렬과 인접 리스트를 사용하여 무지향성 그래프를 자료 구조 클래스로 표현할 수 있다

가중치가 있는 무지향성 그래프에 정점과 간선을 추가하기

class UndirectedGraph {
    constructor () {
        this.edges = {};
    }

    addVertext(vertex) {
        this.edges[vertex] = {};
    }

    addEdge(vertex1, vertex2, weight) {
        if (weight === undefined)
            weight = 0;
        this.edges[vertex1][vertex2] = weight;
        this.edges[vertex2][vertex1] = weight;
    }

    removeEdge(vertex1, vertex2) {
        if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) 
            delete this.edges[vertex1][vertex2]
        if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined)
            delete this.deges[vertex2][vertex1]
    }

    removeVertex = function(vertex) {
        for (let adjacentVertex in this.edges[vertex]) {
            this.removeEdge(adjacentVertex, vertex);
        }
        delete this.edges[vertex];
    }
}

정점간에 방향이 있는 지향성 그래프를 구현하기

class DirectedGraph {
    constructor() {
        this.edges = {};
    }

    addVertex(vertex) {
        this.edges[vertex] = {};
    }

    addEdge(origVertex, destVertex, weight) {
        if(weight === undefined)
            weight = 0;

        this.edges[origVertex][destVertex] = weight;
    }

    removeEdge(origVertex, destVertex) {
        if(this.edges[origVertex] && this.edges[origVertex][destVertex] !== undefined)
            delete this.deges[origVertex][destVertex];
    }

    removeVertex(vertex) {
        for (let adjacentVertex in this.edges[vertex])
            this.removeEdge(adjacentVertex, vertex);
        delete this.edges[vertex];
    }

    traverseBFS(vertex, fn) {
        let queue = [], visited = {};
        queue.push(vertex);

        while(queue.length) {
            vertex = queue.shift();
            if(!visited[vertex]) {
                visited[vertex] = true;
                fn(vertex);
                for (let adjacentVertex in this.edges[vertex]) {
                    queue.push(adjacentVertex);
                }
            }
        }
    }

    traverseDFS(vertex, fn) {
        let visited = {};
        this._traverseDFS(vertex, visited, fn);
    }

    _traverseDFS(vertex, visited, fn) {
        visited[vertex] = true;
        fn(vertex);
        for (let adjacentVertex in this.edges[vertex]) {
            if(!visited[adjacentVertex])
                this. _traverseDFS(adjacentVertex, visited, fn)
        }
    }
}

가중치가 있는 그래프와 최단 경로
다익스트라 알고리즘은 목적지에 도달하기 위해 각 단계에서 최단 경로를 취하는 방식으로 동작한다

처음에는 일부 노드에 도달할 수 없을 수도 있기 때문에 거리를 무한으로 표기한다

function _isEmpty(obj) {
    return Object.keys(obj).length === 0;
}

function _extractMin(Q, dist) {
    let minimumDistance = Infinity,
        nodeWithMinimumDistance = null;
    for (let node in Q) {
        if (dist[node] <= minimumDistance) {
            minimumDistance = dist[node];
            nodeWithMinimumDistance = node;
        }
    }
    return nodeWithMinimumDistance;
}
// class DirectedGraph 내부라고 가정
    Dijkstra(source) {
        let Q = {}, dist = {};
        for (let vertex in this.edges) {
            dist[vertex] = Infinity;
            Q[vertex] = this.edges[vertex];
        }
        dist[source] = 0;

        while (!_isEmpty(Q)) {
            let u = _extractMin(Q, dist);
            delete Q[u];

            for (var neighbor in this.edges[u]){
                let alt = dist[u] + this.edges[u][neighbor];
                if (alt < dist[neighbor]) 
                    dist[neighbor] = alt;
            }
        }
        return dist;
    }

위상 정렬 알고리즘은 순서를 기록하기 위해 스택을 사용하는 수정된 버전의 깊이 우선 정렬

이 알고리즘은 어떤 노드로부터 깊이 우선 정렬을 수행해 해당 노드와 연결된 모든 노드들을 재귀적으로 방문하면서 해당 노드들을 스택에 추가한다

// class DirectedGraph 내부라고 가정
    topologicalSortUtil(v, visited, stack) {
        visited.add(v);
        for (let item in this.edges[v]){
            if (visited.has(item) === false) {
                this.topologicalSortUtil(item, visited, stack)
            }
        }
        stack.unshift(v);
    }

    topologicalSort() {
        let visited = new Set(), stack = [];

        for (let item in this.edges) {
            if (visited.has(item) === false) {
                this.topologicalSortUtil(item, visited, stack);
            }
        }
        return stack;
    }

21-03-14 자바스크립트로 하는 자료구조와 알고리즘(9)

16장 힙

17장 그래프

Harry Kim