<div id="readability-page-1" class="page"><div><p>신춘 시즌이 끝나 다시 개발로 돌아왔다...! </p>
<h2 id="heap">Heap</h2>
<ul>
<li>피라미드 모양으로 쌓아 올린 더미</li>
<li>항상 가장 위에 있는 것을 우선 꺼내는 구조</li>
<li>부모 노드는 자식 노드보다 우선순위가 높음</li>
</ul>
<p>힙은 트리 기반 자료구조다. 힙은 크게 두 가지로 나뉘는데 Max heap과 Min heap이 있다.</p>
<ul>
<li>Max heap : 부모 노드가 항상 자식 노드보다 크거나 같음</li>
<li>Min heap : 부모 노드가 항상 자식 노드보다 작음 (루트가 전체 노드 중 최소값)</li>
</ul>
<p>일반적으로 힙은 이진트리로 구현한다. </p>
<ul>
<li>이진트리 : 각각의 부모 노드가 오직 두 개의 자식 노드만 가지는 트리. </li>
</ul>
<p>힙은 완전 이진트리를 사용한다.</p>
<ul>
<li>완전 이진 트리 : 트리의 가장 아래 층을 제외하고 모든 레벨이 완전히 채워진 트리</li>
</ul>
<p>즉, </p>
<ol>
<li>부모 노드는 항상 자식 노드보다 값이 작다</li>
<li>트리의 레벨에 모든 노드가 있어야 다음 레벨이 생성될 수 있다.</li>
</ol>
<p>두 가지 조건을 지키는 자료구조가 힙(Min heap)이다. </p>
<p>힙은 이진트리지만 배열로도 구현할 수 있는데 아래와 같다. </p>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/2a63b65f-0431-4775-b7c4-efba246bafb1/image.png"></p>
<p>(출처 : <a href="https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9">https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9</a>)</p>
<h4 id="why-heap">why heap</h4>
<p>힙은 이진탐색을 하기 때문에 O(logn)이 걸린다. 만약 배열/연결 리스트로 구현하게 되면 선형탐색으로 O(n)의 시간복잡도가 생기는 것에 비해 매우 효율적</p>
<p>Min heap은 항상 최상위 부모 노드에 최소값이 있다. 그래서 최상위 노드만 조회하면 최소 값을 얻을 수 있다. O(1)의 시간복잡도를 가진다. 특성상 우선순위 큐를 구현하는데 최적의 자료구조고 아래와 같은 곳에서 사용이 가능하다. </p>
<ol>
<li>우선순위 큐 구현</li>
<li>운영체제에서 스케쥴링</li>
<li>다익스트라 알고리즘</li>
</ol>
<h4 id="min-heap-구현하기">Min Heap 구현하기</h4>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/9ada9c07-908b-4569-af1a-aaf04ecb3510/image.png"></p>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/9cae5dec-170c-4737-877d-9f7254696059/image.png"></p>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/10c3909c-262c-4bb0-a99f-8f13d309c0b6/image.png"></p>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/6dcc1280-4720-47ab-8346-4367bc1d627c/image.png"></p>
<ul>
<li>최소값을 꺼내는 삭제는 아래와 같이 진행됨</li>
</ul>
<ol>
<li>최상위 노드를 꺼냄</li>
<li>배열 요소가 2개 이상이라면 끝에 있는 노드를 최상위 부모 노드로 만듦</li>
<li>최근 자리가 최상위 부모로 바뀐 노드의 올바른 위치를 찾기 위해 위에서부터 아래로 내려가면서 찾는 함수 heapifyDown 실행</li>
</ol>
<p><img src="https://velog.velcdn.com/images/dongha1992/post/6039f90e-57c2-48f7-b63b-4d3e5c04aae0/image.png"></p>
<p>으렵네...</p>
<h4 id="참고">참고</h4>
<p><a href="https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9">https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9</a></p></div></div>

삶도 재입학이 되나요?

신춘 시즌이 끝나 다시 개발로 돌아왔다...! 
Heap
피라미드 모양으로 쌓아 올린 더미
항상 가장 위에 있는 것을 우선 꺼내는 구조
부모 노드는 자식 노드보다 우선순위가 높음
힙은 트리 기반 자료구조다. 힙은 크게 두 가지로 나뉘는데 Max heap과 Min heap이 있다.
Max heap : 부모 노드가 항상 자식 노드보다 크거나 같음
Min heap : 부모 노드가 항상 자식 노드보다 작음 (루트가 전체 노드 중 최소값)
일반적으로 힙은 이진트리로 구현한다. 
이진트리 : 각각의 부모 노드가 오직 두 개의 자식 노드만 가지는 트리. 
힙은 완전 이진트리를 사용한다.
완전 이진 트리 : 트리의 가장 아래 층을 제외하고 모든 레벨이 완전히 채워진 트리
즉, 
부모 노드는 항상 자식 노드보다 값이 작다
트리의 레벨에 모든 노드가 있어야 다음 레벨이 생성될 수 있다.
두 가지 조건을 지키는 자료구조가 힙(Min heap)이다. 
힙은 이진트리지만 배열로도 구현할 수 있는데 아래와 같다. 
(출처 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9)
why heap
힙은 이진탐색을 하기 때문에 O(logn)이 걸린다. 만약 배열/연결 리스트로 구현하게 되면 선형탐색으로 O(n)의 시간복잡도가 생기는 것에 비해 매우 효율적
Min heap은 항상 최상위 부모 노드에 최소값이 있다. 그래서 최상위 노드만 조회하면 최소 값을 얻을 수 있다. O(1)의 시간복잡도를 가진다. 특성상 우선순위 큐를 구현하는데 최적의 자료구조고 아래와 같은 곳에서 사용이 가능하다. 
우선순위 큐 구현
운영체제에서 스케쥴링
다익스트라 알고리즘
Min Heap 구현하기
최소값을 꺼내는 삭제는 아래와 같이 진행됨
최상위 노드를 꺼냄
배열 요소가 2개 이상이라면 끝에 있는 노드를 최상위 부모 노드로 만듦
최근 자리가 최상위 부모로 바뀐 노드의 올바른 위치를 찾기 위해 위에서부터 아래로 내려가면서 찾는 함수 heapifyDown 실행
으렵네...
참고
https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9

우선순위 큐

댓글