臀部とバイナリの位置合わせ

37114 ワード

テキストリンク

お尻

hipは、「親値が常に子値より大きい」条件を満たす完全なバイナリツリーです.
親要素の値が常に子要素より小さい場合はhipと呼ばれます(親要素と子要素の関係が変わらない場合のみ)
つまり、お尻には最小お尻と最大お尻の2種類があります.

特長

臀部は半整列状態(非完全整列)

にある.
挿入/削除

はO(logn)であり、非常に速い

である.

は、一般的なアレイ優先キューを用いる

を実施する.

インプリメンテーション

は、一般的なアレイ優先キューを用いる

を実施する.

の最初のインデックスで開始すると、サブノードは2、2+1

として表す.

のブランチが完了し、サブノードの親ノードインデックスは/2として表すことができます.

最小ヒップ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class MinHeap {
	public static class minHeap {
		
		private ArrayList<Integer> heap;
		
		// 힙 생성자
		public minHeap() {
			heap = new ArrayList<>();
			heap.add(0);
		}
		
		// 삽입
		public void insert(int val) {
			heap.add(val);
			int p = heap.size() - 1;
			
			// 힙 사이즈 - 1이 1보다 작아질 때까지 진행 -> root로 이동
			while(p > 1 && heap.get(p / 2) > heap.get(p)) {
				System.out.println("swap");
				// 부모보다 자식 노드가 더 작으면 바꿔야 함 (최소힙)
				int tmp = heap.get(p/2);
				heap.set(p/2, heap.get(p));
				heap.set(p, tmp);
				
				p = p / 2; // p는 부모 값으로 변경(부모 노드 인덱스로 이동)
			}
		}
		
		// 삭제
		public int delete() {
			// 힙 사이즈 - 1이 1보다 작으면 0 리턴
			if(heap.size() - 1 < 1) {
				return 0;
			}
			
			// 삭제할 노드는 루트 노드임
			int deleteItem = heap.get(1);
			
			// root에 가장 마지막 값 넣고 마지막 값 삭제
			heap.set(1, heap.get(heap.size() - 1));
			heap.remove(heap.size() - 1);
			
			int pos = 1;
			while((pos * 2) < heap.size()) {
				int min = heap.get(pos * 2);
				int minPos = pos * 2;
				
				if(((pos*2 + 1) < heap.size()) && min > heap.get(pos*2 + 1)) {
					min = heap.get(pos*2 + 1);
					minPos = pos * 2 + 1;
				}
				
				if(heap.get(pos) < min)
					break;
				
				// 부모 자식 노드 교환
				int tmp = heap.get(pos);
				heap.set(pos, heap.get(minPos));
				heap.set(minPos, tmp);
				pos = minPos;
			}
			
			return deleteItem;	
		}
	}
	
	public static void main(String[] args) throws Exception, IOException {
		System.out.println("start");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		minHeap heap = new minHeap();
		
		for(int i = 0; i<N; i++) {
			int val = Integer.parseInt(br.readLine());
			
			if(val == 0 ) {
				System.out.println(heap.delete());
			} else {
				heap.insert(val);
			}	
		}
	}
}

最大ヒップ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class MaxHeap {
	public static class maxHeap {
		
		private ArrayList<Integer> heap;
		
		// 힙 생성자
		public maxHeap() {
			heap = new ArrayList<>();
			heap.add(1000000); // 인덱스 1부터 시작하기 위함
		}
		
		// 삽입
		public void insert(int val) {
			heap.add(val);
			int p = heap.size() - 1;
			
			// 루트까지 이동, 자식노드가 더 크면 swap
			while(p > 1 && heap.get(p / 2) < heap.get(p)) {
				System.out.println("swap");
				int tmp = heap.get(p/2);
				heap.set(p/2, heap.get(p));
				heap.set(p, tmp);
				
				p = p / 2; // p는 부모 값으로 변경(부모 노드 인덱스로 이동)
			}
		}
		
		// 삭제
		public int delete() {
			// 힙 사이즈 - 1이 1보다 작으면 0 리턴
			if(heap.size() - 1 < 1) {
				return 0;
			}
			
			// 삭제할 노드는 루트 노드임
			int deleteItem = heap.get(1);
			
			// root에 가장 마지막 값 넣고 마지막 값 삭제
			heap.set(1, heap.get(heap.size() - 1));
			heap.remove(heap.size() - 1);
			
			int pos = 1;
			while((pos * 2) < heap.size()) {
				int max = heap.get(pos * 2);
				int maxPos = pos * 2;
				
				if(((pos*2 + 1) < heap.size()) && max < heap.get(pos*2 + 1)) {
					max = heap.get(pos*2 + 1);
					maxPos = pos * 2 + 1;
				}
				
				if(heap.get(pos) > max)
					break;
				
				// 부모 자식 노드 교환
				int tmp = heap.get(pos);
				heap.set(pos, heap.get(maxPos));
				heap.set(maxPos, tmp);
				pos = maxPos;
			}
			
			return deleteItem;	
		}
	}
	
	public static void main(String[] args) throws Exception, IOException {
		System.out.println("start");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		maxHeap heap = new maxHeap();
		
		for(int i = 0; i<N; i++) {
			int val = Integer.parseInt(br.readLine());
			
			if(val == 0 ) {
				System.out.println(heap.delete());
			} else {
				heap.insert(val);
			}	
		}
	}
}