Karteikarten
Heaps
Karten in diesem Stapel (17)
- 1define a priority queuenext element to be removed is the one with greatest priority
implement with a heap - 2define a complete binary treebinary tree of height h is complete if every level L less than h has the max number (2^L) of nodes, and in level h all nodes are as far to the left as possible
- 3define a heapa complete binary tree with a key at each node, such that they keys are comparable and satisfy the property that each node's key is less than the keys of its children. (min heap)
max heap is opposite.
two ops: add and remove - 4define add operationcreate a new node and insert it in the next available position of the complete tree. If level h is not full, then we insert it next to the rightmost leaf. If level h is full, then we start a new level at height h + 1. Then we can just swap the keys of the node and its parent. We then need to repeat the same test on the new parent node, etc, until we reach either the root, or until the key of the parent node is less than the key of the current node. This process of moving a node up the heap, is often called “upheap".
- 5add(key) alg
- 6define removeMin operationremove the root
first copy the last key in the heap (the rightmost key in level h) into the root delete the node containing this last key start at the root, which contains a key that was previously the rightmost leaf in level h. We compare the root to its two children. If the root is greater than at least one of the children, we swap the root with the smaller child - 7removeMin alg
- 8This array representation defines a simple relationship between a tree node's index and its children's index. If the node index is i, then its children have indices --- and ---. Similarly, if a non-root node has index i then its parent has index ---.This array representation defines a simple relationship between a tree node's index and its children's index. If the node index is i, then its children have indices 2i and 2i + 1. Similarly, if a non-root node has index i then its parent has index i=2.
- 9add(key) alg with array implementation
- 10building a heap
- 11best case of building heapbest case: node i that we add satisfies the heap properties immediately and no swapping with parents is necessary
building a heap takes time proportional to the number of nodes n so, best case is O(n). - 12worst case of building heap
- 13removeMin alg with array implementation
- 14downheap alg
- 15define heapsortAn algorithm for sorting “in place":
We repeatedly remove the minimum key the heap, reducing the size of the heap by one each time. This frees up a slot in the array, and so we
insert the removed key into that freed up slot. This yields the keys sorted in the reverse order. That's easy tofi x afterwards: just reverse the order of the keys. - 16heapsort alg
- 17time complexity for heapsort
Informationen
- Beschreibung
- Computer Science Karteikarten am Heaps, erstellt von Virginie Gagné am 15/04/2022.
- Erstellt von
- Virginie Gagné
- Aufrufe
- 1
- Bewertung