늦깎이 IT

[알고스팟 RUNNINGMEDIAN URL] [참고할만한 알고리즘 이론]2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬 이 문제를 풀기 위해서 다음과 같은 조건을 수립합니다.1) 입력받는 데이터들을 두 개의 힙으로 나누되 하나는 최소힙, 나머지 하나는 최대힙으로 구성한다.2) 최대힙의 크기는 최소힙과 같거나 1만큼 크다.3) 최대힙의 루트는 최소힙의 루트보다 작거나 같다. 예를 들어, 3, 1, 5, 4, 2의 순서로 데이터가 입력된다고 가정합니다. 1. 데이터 3이 입력되었을 때1) maxHeap과 minHeap 크기가 같으므로 maxHeap에 저장합니다. 2. 데이터 1이 입력되었을 때1) maxHeap의 크기와 minHeap..

힙 정렬 내용은 2019/04/16 - [늦깎이 IT] - [정렬] 힙 정렬 (수정) :: 늦깎이 IT 에서 다시 수정하여 포스팅하였습니다. 지난 번 힙 기반의 우선순위 큐를 구현한데 이어, 오늘은 힙 정렬을 구현하겠습니다. 힙에 대한 설명은 아래 포스팅을 참고하시기 바랍니다.2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙 [관련 알고리즘 문제]2019/02/17 - [알고리즘 문제/알고스팟] - [알고스팟 RUNNINGMEDIAN] 변화하는 중간값 우선 힙은 1차원 배열로 표현할 수 있습니다. 우리가 보기에는 '완전 이진 트리'인 힙의 구조가 어떻게 배열로표현할 수 있는지 생각해봅시다. 다음과 같이 무작위 데이터가 저장된 배열과 완전 이진트리가 있다고 가정해봅시다.위의 배열과 트리의 연관..