Abstract data type: object + operations(OPS)
- does not tell you how to implement it
Data Structure: specific implementation of an ADT
Example: ADT: Priority queues (PQ)
Object: Set of elements with keys
OPS:
insert (s, x) : S S ∪ {x}
Max (s): Return an element with max priority from S
Extract_Max: Returns Max(s) and S S - Max(s)
Some simple data structures for priority queues:
- Unordered linked list
- Insert(s,x) : Ɵ (1)
- Max(s) : Ɵ (n)
- Ordered Linked List
- Insert(s,x): Ɵ (n)
- Max(s): Ɵ (1)
We want Insert(s,x) : Ɵ (log n) and Extract_Max(s) : Ɵ (log n) and Max: Ɵ (1)
Visual Description:
A Complete Binary Tree : Root node is level 0, 2^0 = 1. Every level L, except possibly the last one has 2^L nodes.
At the bottom level, all nodes are as far to the left as possible. The complete binary tree above
has 9 nodes(n = 9).
A CBT with n nodes has height of 2log n⌋
Height(T) = length of the longest path from the root of T to a leaf.
Max_Heap: the n elements of S are stored in a CBT of n nodes such that :
- Priority of each node ≥ Priority of its children. For Example
- S = 3, 4, 5, 7, 7, 9, 9, 12, 17
Since the tree is not unique, one example of S turning into a tree would be:[17, 9,
12, 7, 7, 9, 5, 3, 4] Putting the elements into a tree in order TLR
Let A be an array that is heapified :
index: 1 2 3 4 5 6 7 8 9
A: 17 9 12 7 7 9 5 3 4
Left Child of A[i] is A[2i]
RIght child of A[i] is A[2i+1]
Parent of A[i] is A[⌊i/2⌋]
Heap Ops:
- Keep the shape(CBT)
- Max heap property has to be satisfied
(A) Insert(A, x), Let's say Insert(A, 13)
1) increment the heap size

More
Less