Heap

2023. 5. 3. 15:31· 자료구조 알고리즘/이론
목차
  1. 특징
  2. 종류
  3. max heap 에서 부모와 자식과의 index 관계
  4. 삽입
  5. 삭제
  6. References
  • stack : LIFO
  • queue : FIFO
  • priority queue : 가장 우선순위가 높은 데이터부터 출력
    • 네트워크 트래픽 제어, os에서 작업 스케줄링
    • 배열, 연결리스트, 힙으로 구현가능하나 힙이 제일 효율적

특징

  • 우선순위 큐를 위해 만들어진 자료구조
  • 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조
  • 중복값 허용

종류

  • max heap: 부모 >= 자식, 완전 이진 트리(왼쪽부터 차례대로 채워져있는 트리)
  • min heap: 부모 <= 자식, 완전 이진 트리

max heap 에서 부모와 자식과의 index 관계

  • left child = parent * 2
  • right child = parent * 2 + 1
  • parent = child / 2

삽입

  1. 힙의 마지막 노드에 삽입
  2. 재구성

삭제

  1. 루트 노드 삭제
  2. 삭제된 루트 노드 자리에 마지막 노드를 넣음
  3. 재구성

 

References

https://github.com/gyoogle/tech-interview-for-developer

 

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖. Contribute to gyoogle/tech-interview-for-developer development by creating an account on GitHub.

github.com

 

728x90
반응형

'자료구조 알고리즘 > 이론' 카테고리의 다른 글

Trie  (0) 2023.05.05
Hash  (0) 2023.05.05
Binary Search Tree  (0) 2023.05.03
Tree  (0) 2023.05.03
array vs (array)list vs linkedlist  (0) 2023.05.02
  1. 특징
  2. 종류
  3. max heap 에서 부모와 자식과의 index 관계
  4. 삽입
  5. 삭제
  6. References
'자료구조 알고리즘/이론' 카테고리의 다른 글
  • Hash
  • Binary Search Tree
  • Tree
  • array vs (array)list vs linkedlist
내공얌냠
내공얌냠
내공냠냠
내공얌냠
내공냠냠
내공얌냠
전체
오늘
어제
  • 분류 전체보기 (254)
    • 개발 (113)
      • mediapipe (16)
      • insightface (5)
      • JongjuAR (3)
    • 자료구조 알고리즘 (79)
      • 코딩테스트 (64)
      • 이론 (15)
    • 공부 (7)
      • 단행본 (7)
      • 튜토리얼 (19)
      • 논문 (15)
      • 복기 (5)
    • 참여 (5)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • 플러터
  • torchscript vs onnx vs tensorrt
  • flutter tutorial
  • vscode 스프링 설치
  • flutter 행사
  • 머신러닝이란
  • 컴퓨터 비전
  • mediapipe translate
  • git tutorial
  • 컴퓨터 비전 기초
  • 구글 미디어파이프
  • google mediapipe
  • flutter 행사 후기
  • speaker adaptation tts
  • flutter conference
  • 플러터 튜토리얼
  • kubeflow설치안됨
  • 미디어파이프
  • python telegrambot
  • 컴퓨터 비전 책 추천
  • 깃 튜토리얼
  • mediapipe
  • ios google places api
  • 딥러닝 기반 음성인식 기초
  • postgresql install in mac
  • flutter
  • 음성인식 기초
  • kubeflow설치가이드
  • postgresql 재설치
  • 음성인식 튜토리얼

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
내공얌냠
Heap
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.