Channi Studies

Treap BasicsA BST built from inserts of N nodes having random-ordered keys stays well-balanced and thus has near-minimum height, meaning searches, inserts, and deletes are O(logN).Because insertion order may not be controllable, a data structure that somehow randomizes BST insertions is desirable. A treap uses a main key that maintains a binary search tree oderering property, and a secondary ke..

Priority Queue ADTA priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.The priority queue enqueue operation inserts an item such that the item is closer to the front thatn all items of lower priority, and closer to the end than all items of equal or higher priority.The priority queue dequeue..

Abstract Data Type과 Data Structure는 헷갈리지만 분명히 다른 것을 의미합니다. 이번 포스트에서는 정확히 그 둘의 차이점에 대해서 알아보겠습니다. Abstract Data TypeAbstract, 즉 추상적 모델로 해당 자료형이 제공해야 할 연산(operations)과 그 의미(semantics)에만 집중합니다. 메모리 배치, 알고리즘과 같은 내부 구현은 추상화(감춰짐)되고, 인터페이스와 동작 규격만 명시합니다. 예를 들면 스택(Stack) ADT는 push, pop, top 등의 연산과 LIFO의 성질만 정의됩니다. Data StructureADT를 구현하기 위한 구체적 방법입니다. 메모리 내 요소 저장 방식(배열, 연결 리스트 등)과 연산 알고리즘을 명시합니다.예를 들어..

Heapify OperationHeapsort is a sorting algorithm that takes advantage of a max-heap's properties by repeatedly removing the max and building a sorted array in reverse order. An array of unsorted values must first be converted into a heap. The heapify opeartion is used to turn an array into a heap. Since leaf nodes already satisfy the max heap property, heapifying to build a max-heap is achieved ..