힙정렬 2

[ BOJ ][JAVA][1655] 가운데를 말해요

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.1 초 (하단 참고) 128 MB 17909 5112 3962 31.605% 문제 수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야..

[ 개념 ] 27. Heap Sort(힙 정렬)

> 힙 정렬 Heap Sort 최악의 경우 시간복잡도 O(nlogn) Sorts in place - 추가 배열 불필요 merge sort도 최악의 경우 O(nlogn)이었지만, 추가 배열이 필요햇음 이진 힙(binary heap) 자료 구조를 사용 O(nlogn)의 시간복잡도를 가지면서 merge sort처럼 추가적인 배열이 필요하지 않기 때문에 좋은 정렬 알고리즘 중 하나이다. Heap의 정의 Heap은 완전 이진 트리(complete binary tree)이면서 Heap property를 만족해야한다. 동일한 데이터를 가진 서로 다른 힙이 존재할 수 있다. 즉, 힙은 유일하지 않다.(같은 원소들을 가지는데 다른 위치에 가진다.) 힙은 일차원 배열로 표현가능하다. `A[1...n]1 루트 노드 : A[..