✍️
TIL
  • TIL
  • react
    • react 16.3 이후 라이프 싸이클
    • 함수형 컴포넌트 vs 클래스 컴포넌트
    • React의 장점
    • 기본문법
    • Flow Diagram
    • redux-saga
    • nextjs
    • mobx
    • 리액트는 어떻게 동작할까?
  • data-structure
    • 이진 검색 트리(binary search tree)
    • HashTable
    • Tree
    • 트라이(Trie)
    • 선형 구조 vs 비선형 구조
    • 연결 리스트(linked-list)
    • Queue
    • Graph
    • Heap
    • Stack
  • web
    • 웹 브라우저의 동작 원리
    • Basic
    • Webpack이란?
    • rendering
    • npm
    • babel
  • graphQL
    • Query
    • Mutation
    • Introduction
  • algorithm
    • big-o
    • 버블 정렬(bubble sort)
    • 힙 정렬(heap sort)
    • 선택 정렬(selection sort)
    • 퀵 정렬(quick sort)
    • 백트래킹 알고리즘
    • 삽입 정렬(insertion sort)
    • 계수 정렬(counting sort)
    • 다엑스트라 알고리즘
    • 이진 탐색
    • 합병 정렬(merge-sort)
    • 동적 계획법(Dynamic programming)
  • web-security
    • XSS(Cross Site Scripting)
    • CSRF(Cross-site request forgery)
    • Tabnabbing
  • javaScript
    • dom
    • 자바스크립트 성능 최적화
    • Event Loop
    • Snippets
    • javaScript
  • programming-paradigm
    • Object Oriented Programming
    • 함수형 프로그래밍
    • 구조적 프로그래밍
  • computer-science
    • Process vs Thread
    • 비트 연산자
    • 그레이 코드
  • vue
    • Vue
  • design-pattern
    • MVP pattern
    • Flux
    • 아토믹 디자인
    • MVVM pattern
    • MVC pattern
  • css
    • css
    • Grid
    • css-methodologies
    • FlexBox
  • html
    • html
  • regExp
    • regExp
  • git
    • Git-flow
Powered by GitBook
On this page
  • 종류
  • 최대 힙(max heap)
  • 최소 힙(min heap)

Was this helpful?

  1. data-structure

Heap

PreviousGraphNextStack

Last updated 5 years ago

Was this helpful?

  • 힙이란 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 트리(노드가 왼쪽부터 순서대로 들어있는 트리)구조의 자료구조

  • 데이터를 삽입할 때 힙의 밑바닥 가장 오른쪽 위치에 이어서 삽입한뒤 부모 노드들과 서로 교환하여 최대 힙 또는 최소 힙을 만든다

  • 데이터를 제거할 때 가장 위의 루트 노드를 제거하고 힙의 마지막 노드를 가져와서 힙을 재구성한다

시간 복잡도 = 힙을 생성할 때: O(nlogn) 데이터를 삽입, 제거할 때: O(logn) 최대, 최소값을 구할 때: O(1)

종류

최대 힙(max heap)

부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙

최소 힙(min heap)

부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙

// 최대 힙
class Heap {
  constructor(list = []) {
    this.list = list

    for (let i = Math.floor(list.length / 2); i >= 0; i--) {
      this.siftDown(i, list.length)
    }
  }

  heapify(idx) {
    const parent = Math.floor((idx - 1) / 2)
    if (this.list[idx] > this.list[parent]) {
      this.swap(idx, parent)
      this.heapify(parent)
    }
  }

  siftDown(idx, length) {
    const left = idx * 2 + 1
    const right = idx * 2 + 2
    let largest = idx

    if (left < length && this.list[left] > this.list[largest]) {
      largest = left
    }
    if (right < length && this.list[right] > this.list[largest]) {
      largest = right
    }
    if (idx !== largest) {
      this.swap(largest, idx)
      this.siftDown(largest, length)
    }
  }

  insert(data) {
    const length = this.list.length
    this.list[length] = data
    this.heapify(length)
  }

  delete() {
    if (!this.list.length) {
      return false
    }
    const item = this.list[0]
    this.list[0] = this.list.pop()
    this.siftDown(0, this.list.length)
    return item
  }

  peek() {
    return this.list
  }

  swap(indexOne, indexTwo) {
    const temp = this.list[indexOne]
    this.list[indexOne] = this.list[indexTwo]
    this.list[indexTwo] = temp
  }
}

const heap = new Heap([1, 2, 3, 4, 9, 6, 7, 8, 0])
heap.insert(99)
heap.insert(10)
heap.delete()
heap.peek() // [ 10, 9, 7, 4, 8, 6, 3, 1, 0, 2 ]
max heap img
min heap img