weekly ps

Table of Contents 개요 기본 구조 값 삽입 최대값 삭제 힙 정렬 C++ STL priority_queue 1. 개요 힙은 이진 트리를 활용한 자료구조이며, 종류로는 최소 힙과 최대 힙이 있습니다. 최대 힙을 알면 최소 힙을 만드는 건 어렵지 않으므로, 이 문서에서는 최대 힙을 기준으로 설명하도록 하겠습니다. 최대 힙 자료구조는 기본적으로 아래의 세 연산을 빠르게 수행하기 위한 자료구조입니다. 연산 1) 최대 힙에 새로운 값을 삽입. 연산 2) 최대 힙 안의 최대값을 삭제. 연산 3) 최대 힙 안의 값 중에 최대값 찾기. 이 세 연산을 배열로 간단하게 처리하려고 하면, 삽입은 O(1)로 가능하더라도 최대값을 찾기에서 O(N) 이 필요함을 알 수 있습니다. 배열에서 최대값을 찾기 위해선, 배열..