Algorithm and Data structure: Trees and Heaps (Priority Queues)

Trees

•A tree is a non linear data structure which solve most of the problem in O(log N)
•Trees are very useful in computer science
•The structure of tree itself provides hierarchical grouping of its elements, thus helping programmer to structure problem in hierarchy manner


Binary Tree
•A binary tree is a special type of tree that every node can only have maximum two nodes.
•A binary tree consists of
–A node(call the root node)
–Left and right sub-trees
•Both sub-trees are themselves binary trees
•The nodes at the lowest level of tree (the one with no sub-trees) are call leaves

•In an ordered binary tree:
–The key of all the nodes in the left sub-tree are less than that of the root
–The key of all the nodes in the right sub-tree are greater than that of the root
–The left and right sub-trees are themselves ordered binary trees


Tree Traversal
•There are 3 ways to traverse the tree:
–inOrder
–preOrder
–postOrder


AVL Tree
•An AVL tree were the firstly dynamically balanced trees to be proposed.
•They are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O (log n) search time.
•Addition and deletion operations also take O (log n) time.


Heaps (Priority Queues)
•Although queues may solve FIFO or First Come First Serve problems, there are certain cases, which we need to violate this rules.
•For instance, certain jobs which are more important than the other.
•Those jobs must be given higher priority to be executed first.
•This particular jobs require a special kind of queue known as a priority queue.
•A priority queue is a special type of queue which allows items with special characteristic to be removed from the list first.
•One typical example is to remove item with the smallest value from the list.
•Heap is an example of priority queue.


Binary Heap
•A heap is a binary tree that is completely filled with the possible exception of the bottom level, which is filled from left to right.
•Such a tree is known as a complete binary tree

Basic Heap Operations

DeleteMins are handled in a similar manner as insertion. Finding the minimum is easy; the hard part is removing it. When the minimum is removed, a hole is created at the root (remember that the root contain the minimum value) making the heap one smaller. It follows that the last element X in the heap must move somewhere in the heap. If X can be placed in the hole, then we are done, however this is unlikely happen. In the case of ascending heap, the smallest children of the hole will take over the hole, thus pushing the hold down one level. We repeat this steps until X can be placed in the hole. Thus, our action is to place X in its correct spot along a path from the root containing minimum children.

HeapSort
•One of a popular implementation of heap is HeapSort.
•HeapSort enables sorting in O (N log N) tome, is one of the best Bog-O running time is sorting methods


Advance Heaps
•d-Heap
–A simple generalization is a d-heap, which exactly like binary heap, except that all nodes have d children's (thus, a binary heap is a 2-heap).
–Since a d-heap contain more nodes, it is much shallower tha a binary heap, improving the running time of Insert to O(logd N).
•The most glaring weakness of the heap implementation, aside from the inability to perform Finds, is that combining two heap into one hard operation.
•This extra operation is known as a merge