방앗간

※ TrickleDown 함수 - 루트 제거 과정을 코드로 작성하면 다음과 같습니다. public E remove(){ E tmp = array[0]; swap(0, lastposition--); // 루트와 마지막 노드를 바꿔주고 lastposition 을 줄여 배열에서 제거한다. trickleDown(0); return tmp; } public void trickleDown(int parent){ int left = 2*parent + 1; int right = 2*parent + 2; // 마지막에 왼쪽 자식이 클 때 if (left == lastposition && (((Comparable)array[parent]).compareTo(array[left])= lastpositon) return; ..

※ TrickleUp 함수 - 완전이진트리 이기 때문에 노드의 위치는 다음과 같은 성질을 가진다 children: 2 * parent + 1 혹은 2 * parent + 2 parent: floor((child-1)/2) 위와 같은 성질을 이용하여 노드 추가 과정을 코드로 작성하면 다음과 같다 int lastposition; // 어디까지 요소를 넣었는지 기록하기 위함 E[] array = (E[]) new Object[size]; public void add(E obj){ array[++lastposition] = obj; // 1. 노드 추가 trickleup(lastposition); // 2. trickle up } public void swap(int from, int to){ E tmp = a..

※ 힙: 추가와 제거 - 힙에 새로운 데이터를 추가하거나 제거할 때 힙의 규칙을 지켜야 한다. 최대 힙이면 부모 노드가 자식 노드보다 커야 최소 힙은 자식 노드가 부모 노드보다 커야한다. 노드 추가 1. 비어있는 공간에 노드 추가 2. 부모 노드보다 큰 숫자인지 확인 후 참인 경우 두 노드의 위치를 바꾼다. (trickle up) 루트 제거 1. 루트를 제거한다 2. 트리의 마지막 요소를 루트에 넣어준다 3. 루트에서 시작해 두 자식 중 큰 노드와 바꿔 힙의 규칙을 만족하게 한다. (tricle down) 무언가를 제거할 때 힙에선 항상 루트를 제거해주어야 한다.

※ Tree Levels - 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조 이다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 부모 노드가 자식 노드보다 크면 최대 힙이고 반대라면 최소 힙이다. 가장 큰 숫자가 뿌리에 있도록 하려면 최대 힙, 가장 작은 숫자부터 시작하려면 최소 힙을 사용하면 된다. 요약) parent > children => Max Heap parent Min Heap

※ 힙과 트리 - 가계도처럼 노드를 나무 형태로 연결 구조를 트리라고 한다. 트리에 있는 각각의 요소는 노드이다. 노드는 부모, 자식 형태로 이어진다. 뿌리(root): 트리의 시작 부분으로 뿌리를 통해 들어가 트리를 탐색한다. 잎(leaf): 자식이 딸려있지 않은 부분입니다. 간선(edge): 두 노드를 연결하는 선입니다.

※ Key 반복자 - 모든 키에 대해 반복해 해시 전체 내용을 살펴본다. 시간 복잡도는 O(n) 이다. // 키에 연결된 연결 리스트의 내용을 살펴보는 함수 class IteratorHelper implements Iterator { T[] keys; int position; // key 반복자 사용 public IteratorHelper() { keys = (T[]) Object[numElements]; int p = 0; for (int i = 0; i < tableSize; i++){

※ resize - 연결 리스트가 너무 길어질 경우 해시 크기를 조절해 주는 resize 함수이다. 크기가 너무 커진경우, 새로운 연결 리스트 배열을 만들고 해시의 모든 연결 리스트에 있는 요소의 키와 값을 각각 찾아야 한다. public void resize(int newSize){ // 새로운 체인 해시 생성

※ getValue 메소드 - 해시에서 키의 값을 찾는 메소드, 키의 index가 무엇인지 찾고 해시에서 해당 index를 찾을 때 까지 반복하며 key의 값이 동일한 경우 키의 값을 반환한다. public V getValue(K key){ // 해당하는 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF; hashval = hashval & tableSize; // 해당 index 찾을 때 까지 반복 for(HashElement he : harray[hashval]){ if(((Comparablekey).compareTo(he.key)==0){ return he.val; } } return null; }

※ add, remove 메소드 - 해시에 내용을 추가하는 add 메소드이다. 크기가 너무 커지거나 작아지는 경우, add 메소드에서 크기 조절을 해주어야만 한다. public boolean add(K key, V value){ // resize if(loadFactor() > maxLoadFactor) resize(tableSize*2); // 키와 값을 저장해 놓을 object he 정의 HashElement he = new HashElement(key, value); // he의 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF; hashval = hashval % tableSize; // add he harray[hashv..

※ 생성자 - 해시의 키와 값을 저장해 줄 내부 클래스 HashElement가 있다면 해시를 구현하는 생성자도 있는데 이는 다음과 같다. public class Hash implements Hashl{ LinkedList[] harray; // 해시 구현 public Hash(int tableSize){ this tableSize = tableSize; harray = (LinkedList[]) new LinkedList[tableSize]; // 형 변환 // 연결 리스트 체이닝 for (int i = 0; i < tableSize; i++) harray[i] = new LinkedList(); maxLoadFactor = 0.75; numElements = 0; } }