데이터 구조의 우선 대기 열 (더미) - 자바
글 목록
대기 열 은 선진 적 인 데이터 구조 로 우선 대기 열의 출 대 는 최소 치 나 최대 치 를 낼 수 있다.
간단히 말 하면 표 list, 대기 열, 스 택 은 모두 배열 로 이 루어 질 수 있 습 니 다.길이 가 배열 의 길 이 를 초과 할 때 두 배 긴 배열 을 새로 만 듭 니 다.
우선 순위 의 기본 상황
1. 우선 대기 열의 주요 작업 우선 대기 열 은 요소 의 용기 이 고 모든 요소 에 관련 된 키 가 있 습 니 다.
insert(key, data): 키 값 을 키 로 하 는 데 이 터 를 우선 대기 열 에 삽입 하고 요 소 는 키 로 정렬 합 니 다.deleteMin/deleteMax: 최소 / 최대 키 의 요 소 를 삭제 하고 되 돌려 줍 니 다.getMinimum/getMaximum: 최소 / 최대 검 지 의 요 소 를 되 돌려 주지 만 삭제 하지 않 습 니 다.2. 우선 대기 열의 보조 동작
k / k : 우선 대기 열 에서 키 를 k 번 째 최소 / 최대 요소 로 되 돌려 줍 니 다. （size）: 우선 대기 열 에 있 는 요소 개 수 를 되 돌려 줍 니 다. （Heap Sort）: 키 값 의 우선 순 위 를 바탕 으로 우선 대기 열 에 있 는 요 소 를 정렬 합 니 다.3. 우선 대기 열의 보조 동작
우선 순위 의 실현 – 더미
우선 대기 열 은 무질서 배열, 무질서 링크, 트 리 등 으로 이 루어 질 수 있 으 며, 더 미 를 사용 하 는 것 이 가장 좋 습 니 다.
뭐 공부 해요?
더 미 는 특정한 성질 을 가 진 이 진 나무 로 쌓 는 기본 적 인 요 구 는 쌓 여 있 는 모든 결점 의 값 이 반드시 (또는 작 거나 같 거나) 그 아이의 결점 의 값 보다 크 거나 같 아야 한 다 는 것 이다. 이것 은 쌓 여 있 는 성질 이 라 고도 부른다.더 미 는 또 다른 성질 이 있다. 즉, h > 0 일 때 모든 잎 결점 은 h 또는 h - 1 층 (그 중에서 h 는 나무의 높이, 완전 이 진 트 리) 에 있다. 즉, 더 미 는 완전 이 진 트 리 여야 한다.
쌓 인 실현
배열
배열 로 쌓 는 것 은 공간 을 낭비 하지 않 을 뿐만 아니 라 일정한 장점 도 가진다.
left child(i) = i * 2;각 결점 의 오른쪽 아 이 는 아래 표 시 된 i 의 2 배 에 1: right child(i) = i * 2 + 1 parent(i) = i / 2 여 기 는 정수 나 누 기 이 고 2 와 3 나 누 기 2 는 모두 1 이다.public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity){ data = new Array<>(capacity); }
public MaxHeap(){ data = new Array<>(); }
//
public int size(){ return data.getSize(); }
// ,
public boolean isEmpty(){ return data.isEmpty(); }
// ，
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}
// ，
private int leftChild(int index){ return index * 2 + 1; }
// ，
private int rightChild(int index){ return index * 2 + 2; }
}
//
public void add(E e){
data.addLast(e);
siftUp(data.getSize() - 1);
}
private void siftUp(int k){
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
data.swap(k, parent(k));
k = parent(k);
}
}
우선 대기 열의 성명
/ 。
Queue priorityQueue = new PriorityQueue<>();
//
Queue priorityQueue = new PriorityQueue<>((a, b) -> b - a);
Priority Queue 가 제공 하 는 구조 방법 에 서 는 사용자 정의 정렬 방법 을 사용 할 수도 있 고 요소 가 자체 적 으로 가지 고 있 는 Comparable 정렬 을 사용 할 수도 있 습 니 다. Priority Queue 는 기본 정렬 을 요구 할 때 요소 대상 이 Comparable 기능 을 가 져 야 합 니 다.
private static Comparator comp =new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
// TODO Auto-generated method stub
return o1.val-o2.val;
}
};
public static ListNode mergeKLists(List lists){
PriorityQueue queue=new PriorityQueue(lists.size(),comp);
}
혹은
PriorityQueue pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
문 제 를 풀다
K 개 정렬 링크 병합
k 개의 정렬 링크 를 합 쳐 합 친 정렬 링크 를 되 돌려 줍 니 다.
사고방식 은 모든 체인 테이블 을 우선 대기 열 에 놓 고 우선 대기 열 을 체인 테이블 로 서열 화한 다.
코드
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
q.add(lists[i]);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!q.isEmpty()) {
tail.next = q.poll();
tail = tail.next;
if (tail.next != null) {
q.add(tail.next);
}
}
return dummy.next;
}
배열 의 K 번 째 최대 요소
public int findKthLargest(int[] nums, int k) {
//
if (0 == nums.length || null == nums || k <= 0 || k > nums.length) {
return -1;
}
// , ,
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (Integer num : nums) {
pq.add(num);
}
for (int i = 0; i < k - 1; i++) {
pq.remove();
}
return pq.peek();
}
데이터 흐름 중위 수
숫자 는 배열 에 계속 들 어 갑 니 다. 매번 새로운 숫자 를 추가 하여 배열 에 들 어 가 는 동시에 현재 새 배열 의 중위 수 를 되 돌려 줍 니 다.
중위 수의 정의:
는 수학 정의 와 같 지 않다.도전:
시간 복잡 도 O (nlogn)
방법 2: 하나의 최소 더미, 하나의 최대 더미 사고: / 데이터 흐름 의 중위 수 를 구하 고 주어진 배열 은 데이터 흐름 을 대표 하 며 하나의 수 를 증가 할 때마다 현재 데이터 집합 중의 중위 수 를 동적 으로 계산 합 니 다. 1. 두 개의 더 미 를 초기 화하 고 가장 큰 더미 와 최소 더 미 를 초기 화 합 니 다.최대 퇴적 데이터 중 비교적 작은 부분의 데이터, 최소 퇴적 데이터 중 비교적 큰 부분의 데이터, 2. 매번 원 소 를 추가 할 때마다 최대 퇴적 원소 > 최소 퇴적 원소 의 개 수 를 판단 한다. 2.1 홀수 라면 최대 퇴적 원소 와 최소 퇴적 원소 의 크기 2.1.1 최대 퇴적 원소 > 최소 퇴적 원소,이 는 최소 부분 에 최대 부분 보다 큰 요소 가 존재 한 다 는 것 을 의미한다. 두 개의 더미 의 꼭대기 요 소 를 교환 해 야 한다. 2.1.2 만약 에 최대 더미 의 꼭대기 요 소 를 < = 최소 더미 의 꼭대기 요 소 를 교환 하면 정상 적 인 것 을 의미한다. 다른 조작 이 필요 없다. 2.2 만약 에 짝수 라면 가장 큰 더미 에서 최대 치 를 나 누 어 최소 더미 에 게 주 고 두 개의 더미 의 개수 차 이 를 유지한다. < = 13. count +
public class Solution {
/**
\* @param nums: A list of integers
\* @return: the median of numbers
*/
private PriorityQueue maxheap,minheap;
private int count=0;
public int[] medianII(int[] nums) {
maxheap=new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
minheap=new PriorityQueue<>();
int len=nums.length;
int []result=new int[len];
for(int i=0;iminheap.peek()){
int maxNum=maxheap.poll();
int minNum=minheap.poll();
maxheap.offer(minNum);
minheap.offer(maxNum);
}
}
}else{
minheap.offer(maxheap.poll());
}
count++;
}
public int getMedian(){
return maxheap.peek();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
물체 검출의 평가 지표 IoU의 계산 방법Yolo나 SSD 등 물체 검출에서 평가 지표로 사용되는 IoU에 대해 조사했으므로 정리했습니다. IoU (Intersection over Union)는 두 영역이 얼마나 겹치는지를 나타내는 지표입니다. 두 영역의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
