Tori의 개발 공부

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42628🛠 문제 상황프로그래머스에서 해당 문제를 풀기 위해서는 최댓값과 최솟값을 모두 O(1)로 조회하면서도 O(log N)으로 삽입/삭제가 가능한 자료구조가 필요했습니다.기존의 단일 우선순위 큐(Heap)만으로는 한쪽 방향의 정렬만 유지할 수 있어, 최댓값과 최솟값을 동시에 효율적으로 관리할 수 없었습니다.✅ 해결 방법최대 힙(Max Heap)과 최소 힙(Min Heap)을 동시에 유지하는 Dual Heap을 구현했습니다. 이중 우선순위 큐는 두 개의 힙을 사용하여 최댓값과 최솟값을 빠르게 찾을 수 있도록 합니다.📌 핵심 아이디어최소 힙(minHeap): 최솟값을 빠르게 조회하기 위한 ..

Heap 이란? 데이터에서 최댓값 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리로 우선순위 큐를 위해 만들어진 자료구조 최대힙(max heap) : 부모노드 ≥ 자식노드 최소힙(min heap) : 부모노드 ≤ 자식노드 💡 완전 이진 트리란? 이진트리 = 자식 노드가 최대 두 개인 트리 완전 이진트리 = 마지막 레벨을 제외한 모든 노드가 2개씩 채워져 있으며, 최하단 레벨 또한 좌측부터 채워져있는 노드를 의미한다. 즉 완전 이진트리는 왼쪽부터 자식 노드를 차례로 채운다. index 성질 heap은 완전 이진 트리 구조이기 때문에 노드 간 인덱스 관계를 나타낼 수 있다. → 완전 이진트리는 무조건 왼쪽부터 채워지기 때문에 채워지는 순서가 있음 = index 부모 노드 index = 자식 노드 index ..