LeetCode 솔루션 분류

파이썬 - 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

컨텐츠 정보

본문

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 

힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

  • 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
  • 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

img.png<출처: ">">">https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>

 

이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 

이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다.

자세한 내용은 아래의 링크를 클릭해주세요

https://littlefoxdiary.tistory.com/3 

https://www.geeksforgeeks.org/heap-data-structure/ 


관련자료

댓글 0
등록된 댓글이 없습니다.
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 916 명
  • 오늘 방문자 5,495 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0