Machineboy空
Ordered Data Structures # WEEK 4 : Heaps 본문
4.1 Heap introduction
제거 연산을 하는 데 걸리는 시간복잡도를 고려하면, 배열이나 리스트는 O(n)이라 굉장히 비효율적.
그렇다면 트리 구조를 생각해보자. 이진 검색트리의 경우 너무나 견고한 규칙에 따라 구성되어있기 때문에 이것 또한 성능 저하를 일으킨다.
그래서 트리의 아이디어를 가져오되, 노드가 우선순위를 가지고 있는 우선순위 큐를 활용한 힙을 만들어 볼 것
the remove operation is not having any parameters, it's simply going to take the minimum value found in the entire data structure, and remove it and return it back to the user. We want to optimize for this to build ourselves something called a Priority Queue, where every single value can have a priority, and we can remove based on the value that has the highest or lowest priority. To understand exactly why we want to build this, we can look at some of the classic data structures.
Unfortunately both of these have an o of n operation, which an operation we'd love to avoid using. Instead, we're going to try and build a data sturcture that we can do both operations in less than o of n time. To do that, we're going to think about using something like a tree. Though the ordering of this tree is not going to be the strictness of a binary search tree. Because remember in a binary search tree, we have detailed explanation of exactly what we need on each side, and we find that that structure's going to lead to some performance decreases that se're not going to find acceptable.
Instead, we can go ahead and build out a new data structure by using the idea of a tree and sticking one property on it. Specifically, we're going to call this new type pf tree a heap, and the heap is going to have a few properties.
- 첫번째 속성 : binary tree
All we care is this local property that the parent is going to be smaller than all of its descendants. This property, we're going to actually represent using a clever data structure because we would ideally love the performance of an unsorted array, some of those all of one great guarantees for lookup that we don't have necessarily on, that we absolutely don't have on a binary search tree. So, what we'll do is we'll always ensure a heap is a complete tree. Remember a complete tree is going to be a perfect tree with every node fill in up until the last level, and in that last level we're going to have all of the nodes pushed to the left.
Once we have a complete tree, we can go ahead and map that tree entirely to a data structure that we're very comfortable with.
4.2 Heap Insert
as part of doing the insert, check to make sure that every level of my minimum heap is balanced and that the minimum heap property maintenance is true.
Grow Array
- check whether or not the array is large enough to accept this element.
- if we don't have room to insert, we need tp grow the array.
When we double the array, notice that our old array is going the contain all of the elments in the blue and orange layer. here when I fill up this last blue layre, I need to expand the array to add an entire new layer of the tree. This is equivalent to doubling the size of the array, by making a left and right child at every single node.
4.3 Heap - RemoveMIN
we are always going to be removing the minimum element. There is no operation on the heap that we can do except for removing that minimum most element. So to do so, we're going to have to figure out the algorithm to take the top element of the tree, the root of the tree itself and actually maintain the heap property even after removing the tree.
So through two really clever algorithms, inserting using heapifyUp, and removing minimum by using heapifyDown, we're able to maintain a minimum heap through a series of simple tree operations that offers us an extremely efficient structure to maintain an ordered insidered array without having to totally ordered array.
4.4 Heap - buildHeap
let's understand why we want to use a heap over other data structures, even though this looks remarkably similar to a binary tree. The main reason we want to use a heap is the idea that we can be really efficient about actually building a heap from the heap operations we have.
Let's think about only using the heapifyDown operation. by only using heapifyDown operation, what we're doing is we're saying that it doesn't actually matter what's in our very last level of the tree. Because the very last level of the tree means that everything here is already balanced.
heapifyDown takes a node and make sure that that node is placed down inside of our tree, in the proper location.
So the key reason that we're actually care about building heaps and that we care about the heap algorithm. is the fact that, given any sort of data structure, any array representation, we can build a heap notation of that in just O of N time.Far shorter than sorting the array, far shorter than inserting into a binary tree.
4.5 Heap - Runtime Analysis
지금까지 힙에 대해 배운 것
- insert and remove operation by just doing simple tree operation
- we can build a heap in O of N time, in linear time, which is a fantastic result
배열과 다른 이진 탐색트리들과 비교해 이점이 무엇이냐면, build하는데 얼마 안걸린다는 거인듯?
Heap Sort
