6063 : 힙 직접 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
힙 직접 구현
1차원 리스트(배열)를 기반으로 이진 트리 구조의 최소힙(Min-Heap)을 직접 구현하시오.
구현해야 할 연산:
-
-
-
참고: 1-indexed 배열을 사용하면 부모/자식 인덱스 계산이 편리합니다.
부모: i//2, 왼쪽 자식: 2i, 오른쪽 자식: 2i+1
[제약 조건]
• 연산 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 입력 정수: $1 \le x \le 10^9$ (정수)
1차원 리스트(배열)를 기반으로 이진 트리 구조의 최소힙(Min-Heap)을 직접 구현하시오.
구현해야 할 연산:
-
push x: 정수 x를 힙에 삽입 (heapify-up 수행)-
pop: 힙에서 최솟값을 추출하고 출력 (heapify-down 수행)-
peek: 힙에서 최솟값을 삭제 없이 조회참고: 1-indexed 배열을 사용하면 부모/자식 인덱스 계산이 편리합니다.
부모: i//2, 왼쪽 자식: 2i, 오른쪽 자식: 2i+1
[제약 조건]
• 연산 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 입력 정수: $1 \le x \le 10^9$ (정수)
입력 설명
첫째 줄에 명령의 수 N (1 ≤ N ≤ 50,000)이 주어집니다.
둘째 줄부터 N개의 줄에 명령(push x, pop, peek)이 주어집니다.
둘째 줄부터 N개의 줄에 명령(push x, pop, peek)이 주어집니다.
출력 설명
pop이나 peek 명령이 들어올 때마다 최솟값을 출력합니다.
빈 힙에서 pop 또는 peek이 호출되면 -1을 출력합니다.
빈 힙에서 pop 또는 peek이 호출되면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
push 3
push 1
push 2
pop
peek
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2