<div id="readability-page-1" class="page"><div><ol>
<li>
<p>힙이란?<br>
이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.</p>
<ul>
<li>우선순위 큐 : 우선 순위가 높은 요소가 먼저 나가는 큐</li>
</ul>
<ul>
<li>주의 : 자료구조가 아닌 개념 고로, 우선순위 큐는 힙이 아니다.</li>
</ul>
</li>
<li>
<p>자료들 중에서 최대, 최소을 찾아내는 방법<br>
- 매 루프마다 함수를 호출 O(n)<br>
- 매 루프마다 정렬 O(n log n)<br>
- Heap 이용 O(log n)<br>
=&gt; 이진 트리의 높이(레이어)가 log n 개이다.<br>
=&gt; 처음에 조금 오해했던 조건을 내 맘대로 넣을 수 있는건 아니다. 왜냐하면 이진 트리이기 때문에 트리로 분리가 되면서 각각 뭉탱이를 갖기 때문에 두번째 레이어의 다른 가지의 값과 다른 세번째 레이어의 값이 크기가 일정하지 않을 수 있다.</p>
</li>
<li>
<p>코테</p>
<ul>
<li>핵심 키워드 : 매번 큰 값, 작은 값</li>
<li>대표문제<br>
- 배상 비용 최소화 실습(강의 내 실습 문제)<br>
<img src="https://velog.velcdn.com/images/2taesung/post/f5243d90-bd95-4439-8935-03b774a21209/image.png"></li>
</ul>
</li>
</ol>
<pre><code>class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 &amp;&amp; this.heap[parentIndex] &lt; value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    if (this.heap.length ===2) return this.heap.pop();

    const returnValue = this.heap[1];
    // 여기에서 마지막 노드(최대가 아닌데도)를 정점으로 끌어 올리는 이유는
    // 자연스럽게 맨 위에 노드를 채워주고 주루룩 내려줘서 이진트리 구조를 유지시키려함에 있다.
    this.heap[1] = this.heap.pop();
    
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (this.heap[currentIndex] &lt; this.heap[leftIndex] ||
          this.heap[currentIndex] &lt; this.heap[rightIndex]) {
      if (this.heap[leftIndex] &lt; this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = (currentIndex * 2) + 1;
    }

    return returnValue;
  }
}

function solution(no, works) {
    if (works.reduce((a, b) =&gt; a + b) &lt;= no) {
        return 0;
    }
    let heap = new MaxHeap();
    for (let a of works) {
        heap.push(a);
    }
    // console.log(heap)
    while (no!==0) {
        no --;
        heap.push(heap.pop() - 1);
    }
    // console.log(heap)
    return heap.heap.reduce((a, b) =&gt; a + b * b);
}</code></pre>
<ul>
<li>심화문제 : </li>
</ul>
<p>출처 : <a href="https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript">https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript</a></p></div></div>

2taesung.log

Taesung Lee

힙이란?
 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.
우선순위 큐 : 우선 순위가 높은 요소가 먼저 나가는 큐
주의 : 자료구조가 아닌 개념 고로, 우선순위 큐는 힙이 아니다.
자료들 중에서 최대, 최소을 찾아내는 방법
매 루프마다 함수를 호출 O(n)
매 루프마다 정렬 O(n log n)
Heap 이용 O(log n)
=> 이진 트리의 높이(레이어)가 log n 개이다.
=> 처음에 조금 오해했던 조건을 내 맘대로 넣을 수 있는건 아니다. 왜냐하면 이진 트리이기 때문에 트리로 분리가 되면서 각각 뭉탱이를 갖기 때문에 두번째 레이어의 다른 가지의 값과 다른 세번째 레이어의 값이 크기가 일정하지 않을 수 있다.
코테
핵심 키워드 : 매번 큰 값, 작은 값
대표문제 
배상 비용 최소화 실습(강의 내 실습 문제)
class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }
  pop() {
    if (this.heap.length ===2) return this.heap.pop();
    const returnValue = this.heap[1];
    // 여기에서 마지막 노드(최대가 아닌데도)를 정점으로 끌어 올리는 이유는
    // 자연스럽게 맨 위에 노드를 채워주고 주루룩 내려줘서 이진트리 구조를 유지시키려함에 있다.
    this.heap[1] = this.heap.pop();
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (this.heap[currentIndex] < this.heap[leftIndex] ||
          this.heap[currentIndex] < this.heap[rightIndex]) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = (currentIndex * 2) + 1;
    }
    return returnValue;
  }
}
function solution(no, works) {
    if (works.reduce((a, b) => a + b) <= no) {
        return 0;
    }
    let heap = new MaxHeap();
    for (let a of works) {
        heap.push(a);
    }
    // console.log(heap)
    while (no!==0) {
        no --;
        heap.push(heap.pop() - 1);
    }
    // console.log(heap)
    return heap.heap.reduce((a, b) => a + b * b);
}
심화문제 : 
출처 : https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript

힙

댓글