후로링의 프로그래밍 이야기

#4 알고리즘 Advanced Data Structure : Binomial Heap

Binomial Heap을 배우기 위해서 Binomial Tree가 어떤 것인지 부터 알아보겠습니다. Binomial Tree Binomial Tree는 우선순위 큐 형태의 자료구조입니다. 아래 그림과 같이 한 Tree의 루트 노드가 다른 루트 노드를 가리키는 형태입니다. 노드의 수는 2^k(루트에 새로 붙여지는 트리와 붙는 트리의 크기가 같다), 루트에 붇기 때문에 높이는 1씩 증가하게되며 트리의 깊이는 K combination i(K에서 i를 뽑는 경우의수), 그리고 루트의 degree가 가장 크게 됩니다. Binomial Heap Binomial Heap의 각각의 Binomial Tree는 min-heap입니다. 그리고 k값이 같은 Binomial Tree는 존재하지 않습니다(차수가 같은 트리가 존..
알고리즘 2017. 2. 22. 00:57
#3 알고리즘 Advanced Data Structure : Binary Heaps

Heap은 기초적인 내용이지만 Binomial Heap을 다루기 위해 내용을 확실히 숙지해야 하므로 설명하고 넘어가도록 하겠습니다. Heap 이란? 다음 조건을 만족하는 key값을 저장한 Binary Tree 입니다. 1. Heap-Order : 모든 노드는 자신의 부모노드보다 작거나 큰 값을 가진다. 2. Complete Binary Tree : 항상 왼쪽부터 꽉 채워져 있는 형태의 Binary Tree여야 한다. Heap과 Priority Queues(우선순위 큐) 우리는 힙을 우선순위 큐, 다시말해 우선순위가 높은것을 먼저 나가게 하는데에 쓸 수 있습니다. Min heap은 key값을 오름차순 정렬 하는데 쓰일 수 있습니다. Heap에서의 Insert 힙에서의 구조적 조건과 순서적 조건을 맞춰주면 ..
알고리즘 2017. 1. 31. 02:30
#2 알고리즘 Advanced Data Structure : Skip List

Data structure 자체가 알고리즘을 구현하는 방법이 될 수 있습니다. Skip List 정렬된 linked list에 대해 적용하는 알고리즘으로 빠른 검색및 삽입 삭제를 가능하게 해주는 자료구조입니다. Skip List는 key와 element쌍으로 되어있는 리스트가 여러 레이어에 걸쳐 있는 형태입니다. 각 레이어는 플러스 무한대와 마이너스 무한대를 항상 키 값으로 가지고있고 가장 하위 레이어인 S0는 오름차순으로 정렬되어 있습니다. 그리고 하위레이어는 상위 레이어를 포함하는 형태입니다. 그림으로 살펴보면 아래 그림과 같습니다. Skip List에서의 Search Skip List에서의 Search는 최상단 list의 첫번째 위치에서부터 시작합니다. 만약 현재 위치의 다음 element가 찾으려..
알고리즘 2017. 1. 30. 05:48
Prev 1 2 3 4 5 6 7 8 Next