Heap

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1034 palavras )
  • Download(s) : 0
  • Publicado : 31 de março de 2013
Ler documento completo
Amostra do texto
Heap Sort Theory

1. For a tree of height h, we know a binary tree is h = lg n-1 so 2^h = n-1. For a height h, the smallest number of elements possible is that 1 element is in the last level of the tree. So this algorithm is 2^(h) number of elements. For a maximum number of elements, the tree will be full and balanced, so the number of elements will be 2^(h+1) – 1. For a example a tree withheight 2, will have 2^(2) nodes or 4 nodes. In the max case the tree will be full and we will have 2^3 -1 or 7 nodes. (Use the tree in answer 3 to see how it looks and count the nodes)

2. The smallest number must be a leaf node, it necessarily doesn’t have to be in the last level of a height h, or necessarily be the last node in the tree. But since the largest number is a parent and itschildren can’t be larger than its parent thus smallest number is a leaf node.

3. To check this we need to first use a small array then consider it at n. So for a 7 element array which is reverse sorted, the heap tree is
[pic]
Which is in fact a heap, for n numbers which is in the array of , we will find out that this tree is indeed a heap as well, since no node underneath the parents will begreater than the parent.

4. is in array form, in a tree form we can determine if this is indeed a heap. [pic]
From looking at the tree, this array is not a heap. The reason involves the left most sub tree. In order for something to be a heap the parents value must be higher or equal to all of its children. For a example 23 is larger than 17 or 14, so that would satisfy a heap. But in thebottom sub tree the parent 6 has 2 values 5 and 7, but 7 is larger than 6, so it isn’t a heap.

5. Heapify (A, 3) on the array A =

[pic]
[pic]
The function calls heapify(A,3), which switches 3 and 10, but now node 6 still violates the heapify, so it calls heapify (A,6). This switches the value of 3 and 9. Now the array is heapified.

6. For heap sort it doesn’t matter if it’s sorted in whatever way. The heap sort still runs in O(n lg n) time no matter what array you use. The reason involves how the heap sort works. For any array the heap sort does the command “build max heap”, this heapifies any array so it can be sorted. That means whether the array is in forward sort, or reverse sort, build max heap will heapify it so it can be used in heap sort. Then heap sort still worksthe same then, since build max heap takes O(n) and max heapify takes O(lg n), then it will always be O(n lg n).

7. The heap sort is split into 2 parts. In order to do heap sort we make a tree which has been heapified, therefore the largest number is in the root. Then we remove this root and create a new tree with the two children, because the new tree may violate the heap property we need 1call to heapify to make sure it stays heaped. Then we recreate the new tree, remove the root heapify it and continue this process until there are 2 elements left. Building the tree takes O(n) time and each of the n-1 calls to heapify takes O(lg n). So the entire algorithm takes O(n lg n)

8. To make a first in first out queue using a priority queue you need to make a few changes to the priorityqueue. In a FIFO, the first element in is the first element out of the queue. In a priority queue, the first element out is always the highest value despite on how its put into the queue. You can think of a FIFO queue as a priority queue where the priority of each item is the amount of time it has spent in the queue. To do this is easy. We make a counter, and every time we enqueue, wedecrement to the counter. The counter becomes the priority of the queue, so when you dequeue, it removes the highest value item.

9. To make a stack using the priority queue is the exact opposite of the FIFO queue. In this case in order for the priority queue to work like a stack each time we push, the latest push must be a higher priority than the earlier push value. If we make a counter and is...
tracking img