[Java]running median 복습하면서 자바로 구현해보기

1. running median 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median (tistory.com) 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median 1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결 deepdata.tistory.com 1) 최대힙과 최소힙 2개를 초기화 2) 최대힙의 원소의 수와 최소힙의 원소의 수가 동일하다면, 최대힙에 수를 넣어주고 3) 최대힙의 원소의 수가 최소힙의 원소의 수 + 1이라면, 최소힙에 수를 넣어준다. 즉 최대힙 > 최소힙 > 최대힙 > 최소힙 >....으로 번갈아가면서 수..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 21.
• textsms

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median

1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결론부터 말하자면, (크기와는 무관하게) 항의 순서대로 수열이 주어질때 최대힙에 들어간 원소의 수와 최소힙에 들어간 원소의 수가 서로 같을 때는 최대힙에 수를 넣어주고 최대힙의 원소의 수가 최소힙의 원소의 수보다 1개 더 많을때는 최소힙에 수를 넣어준다 즉 항상 최대힙 > 최소힙 > 최대힙 > 최소힙 >.. 으로 번갈아가면서 수를 넣어준다. 힙은 완벽하게 정렬해주지는 않지만, 루트에는 최소힙이면 힙에 들어간 원소들 중 최솟값이, 최대힙이면 힙에 들어간 원소들 중 최댓값이 온다는건 확실하다 최대힙에 원소를 넣으면 최대힙..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2022. 10. 18.
• textsms