Channi Studies

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 ..

Heaps and the MaxHeap ClassEach level of a max-heap tree greows from left to right; a new level is added only after the current level fills up completely. Because the tree is nearly full (with at most one level not completely filled), an array implementation is efficient. The array implementation means that the root is always at index 0, and the index of any node's parent and children can be eas..

Heap StorageHeaps are typically stored using arrays. Given a tree representation of a heap, the heap's array form is produced by traversing the tree's levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root's left child is entry at index 1, the root's right child is entry at index 2, and so on. Parents and Child IndicesBecause heaps are ..