1、Analysis of Algorithms CS 477/677,Instructor: Monica Nicolescu,CS 477/677,2,The Heap Data Structure,Def: A heap is a nearly complete binary tree with the following two properties: Structural property: all levels are full, except possibly the last one, which is filled from left to right Order (heap)
2、property: for any node xParent(x) x,Heap,5,7,8,4,It doesnt matter that 4 in level 1 is smaller than 5 in level 2,2,CS 477/677,3,Array Representation of Heaps,A heap can be stored as an array A. Root of tree is A1 Left child of Ai = A2i Right child of Ai = A2i + 1 Parent of Ai = A i/2 HeapsizeA lengt
3、hA The elements in the subarray A(n/2+1) n are leaves The root is the maximum element of the heap,A heap is a binary tree that is filled in order,CS 477/677,4,Maintaining the Heap Property,Suppose a node is smaller than a child Left and Right subtrees of i are max-heaps Invariant: the heap condition
4、 is violated only at that node To eliminate the violation: Exchange with larger child Move down the tree Continue until node is not smaller than children,CS 477/677,5,Building a Heap,Convert an array A1 n into a max-heap (n = lengthA) The elements in the subarray A(n/2+1) n are leaves Apply MAX-HEAP
5、IFY on elements between 1 and n/2,A:,CS 477/677,6,Heapsort,Goal: Sort an array using heap representations Idea: Build a max-heap from the array Swap the root (the maximum element) with the last element in the array “Discard” this last node by decreasing the heap size Call MAX-HEAPIFY on the new root
6、 Repeat this process until only one node remains,CS 477/677,7,Alg: HEAPSORT(A),BUILD-MAX-HEAP(A)for i lengthA downto 2do exchange A1 AiMAX-HEAPIFY(A, 1, i - 1)Running time: O(nlgn),CS 477/677,8,Example: A=7, 4, 3, 1, 2,CS 477/677,9,HEAP-MAXIMUM,Goal: Return the largest element of the heapAlg: HEAP-M
7、AXIMUM(A)return A1,Running time: O(1),Heap A:,Heap-Maximum(A) returns 7,CS 477/677,10,HEAP-EXTRACT-MAX,Goal: Extract the largest element of the heap (i.e., return the max value and also remove that element from the heap Idea: Exchange the root element with the last Decrease the size of the heap by 1
8、 element Call MAX-HEAPIFY on the new root, on a heap of size n-1,Heap A:,CS 477/677,11,HEAP-EXTRACT-MAX,Alg: HEAP-EXTRACT-MAX(A, n)if n 1then error “heap underflow”max A1A1 AnMAX-HEAPIFY(A, 1, n-1) remakes heapreturn max,Running time: O(lgn),CS 477/677,12,Example: HEAP-EXTRACT-MAX,max = 16,Heap size
9、 decreased with 1,Call MAX-HEAPIFY(A, 1, n-1),CS 477/677,13,HEAP-INCREASE-KEY,Goal: Increases the key of an element i in the heap Idea: Increment the key of Ai to its new value If the max-heap property does not hold anymore: traverse a path toward the root to find the proper place for the newly incr
10、eased key,Key i 15,CS 477/677,14,HEAP-INCREASE-KEY,Alg: HEAP-INCREASE-KEY(A, i, key)if key 1 and APARENT(i) Aido exchange Ai APARENT(i)i PARENT(i)Running time: O(lgn),Key i 15,CS 477/677,15,Example: HEAP-INCREASE-KEY,CS 477/677,16,MAX-HEAP-INSERT,Goal: Inserts a new element into a max-heap Idea: Exp
11、and the max-heap with a new element whose key is - Calls HEAP-INCREASE-KEY to set the key of the new node to its correct value and maintain the max-heap property,8,2,4,14,7,1,16,10,9,3,CS 477/677,17,MAX-HEAP-INSERT,Alg: MAX-HEAP-INSERT(A, key, n)heap-sizeA n + 1An + 1 - HEAP-INCREASE-KEY(A, n + 1, k
12、ey),Running time: O(lgn),8,2,4,14,7,1,16,10,9,3,CS 477/677,18,Example: MAX-HEAP-INSERT,CS 477/677,19,Summary,We can perform the following operations on heaps: MAX-HEAPIFY O(lgn) BUILD-MAX-HEAP O(n) HEAP-SORT O(nlgn) MAX-HEAP-INSERT O(lgn) HEAP-EXTRACT-MAX O(lgn) HEAP-INCREASE-KEY O(lgn) HEAP-MAXIMUM
13、 O(1),CS 477/677,20,The Search Problem,Find items with keys matching a given search key Applications: Keeping track of customer account information at a bank Search through records to check balances and perform transactions Keep track of reservations on flights Search to find empty seats, cancel/mod
14、ify reservations Search engine Looks for all documents containing a given word,CS 477/677,21,Symbol Tables (Dictionaries),Dictionary = data structure that supports two basic operations: insert a new item and return an item with a given key Queries: return information about the set Search (S, k) Mini
15、mum (S), Maximum (S) Successor (S, x), Predecessor (S, x) Modifying operations: change the set Insert (S, k) Delete (S, k),CS 477/677,22,Implementations of Symbol Tables,Key-indexed-array Key values are distinct, small numbers Store the items in an array, indexed by keys Ordered/unordered arrays Ord
16、ered/unordered linked lists,Insert,Search,ordered array,ordered list,unordered array,unordered list,N,N,N,N,1,1,N,N,key-indexed array,1,1,CS 477/677,23,Binary Search Trees,Support many dynamic set operations SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT Running time of basic operations on
17、 binary search trees On average: (lgn) The expected height of the tree is lgn In the worst case: (n) The tree is a linear chain of n nodes,CS 477/677,24,Binary Search Trees,Tree representation: A linked data structure in which each node is an object Node representation: Key field Satellite data Left
18、: pointer to left child Right: pointer to right child p: pointer to parent (p root T = NIL) Satisfies the binary-search-tree property,CS 477/677,25,Binary Search Tree Example,Binary search tree property:If y is in left subtree of x, then key y key xIf y is in right subtree of x, then key y key x,CS
19、477/677,26,Traversing a Binary Search Tree,Inorder tree walk: Prints the keys of a binary tree in sorted order Root is printed between the values of its left and right subtrees: left, root, right Preorder tree walk: root printed first: root, left, right Postorder tree walk: left, right, root root pr
20、inted last,Preorder: 5 3 2 5 7 9,Inorder: 2 3 5 5 7 9,Postorder: 2 5 3 9 7 5,CS 477/677,27,Traversing a Binary Search Tree,Alg: INORDER-TREE-WALK(x)if x NILthen INORDER-TREE-WALK ( left x )print key xINORDER-TREE-WALK ( right x ) E.g.:Running time: (n), where n is the size of the tree rooted at x,Ou
21、tput: 2 3 5 5 7 9,CS 477/677,28,Searching for a Key,Given a pointer to the root of a tree and a key k: Return a pointer to a node with key k if one exists Otherwise return NIL Idea Starting at the root: trace down a path by comparing k with the key of the current node: If the keys are equal: we have
22、 found the key If k keyx search in the right subtree of x,CS 477/677,29,Searching for a Key,Alg: TREE-SEARCH(x, k)if x = NIL or k = key xthen return xif k key xthen return TREE-SEARCH(left x, k )else return TREE-SEARCH(right x, k ),Running Time: O (h), h the height of the tree,CS 477/677,30,Example:
23、 TREE-SEARCH,Search for key 13: 15 6 7 13,CS 477/677,31,Iterative Tree Search,Alg: ITERATIVE-TREE-SEARCH(x, k)while x NIL and k key xdo if k key xthen x left xelse x right xreturn x,CS 477/677,32,Finding the Minimum in a Binary Search Tree,Goal: find the minimum value in a BST Following left child p
24、ointers from the root, until a NIL is encountered Alg: TREE-MINIMUM(x) while left x NIL do x left x return x Running time: O(h), h height of tree,Minimum = 2,CS 477/677,33,Finding the Maximum in a Binary Search Tree,Maximum = 20,Goal: find the maximum value in a BST Following right child pointers fr
25、om the root, until a NIL is encountered Alg: TREE-MAXIMUM(x) while right x NILdo x right x return x Running time: O(h), h height of tree,CS 477/677,34,Successor,Def: successor (x ) = y, such that key y is the smallest key key x E.g.: successor (15) =successor (13) =successor (9) =Case 1: right (x) i
26、s non empty successor (x ) = the minimum in right (x) Case 2: right (x) is empty go up the tree until the current node is a left child: successor (x ) is the parent of the current node if you cannot go further (and you reached the root): x is the largest element,17,15,13,CS 477/677,35,Finding the Su
27、ccessor,Alg: TREE-SUCCESSOR(x)if right x NILthen return TREE-MINIMUM(right x)y pxwhile y NIL and x = right ydo x yy pyreturn yRunning time: O (h), h height of the tree,y,x,CS 477/677,36,Predecessor,Def: predecessor (x ) = y, such that key y is the biggest key key x E.g.: predecessor (15) = predecess
28、or (9) = predecessor (13) = Case 1: left (x) is non empty predecessor (x ) = the maximum in left (x) Case 2: left (x) is empty go up the tree until the current node is a right child: predecessor (x ) is the parent of the current node if you cannot go further (and you reached the root): x is the smal
29、lest element,13,7,9,CS 477/677,37,Insertion,Goal: Insert value v into a binary search tree Idea: If key x v move to the right child of x, else move to the left child of x When x is NIL, we found the correct position If v key y insert the new node as ys left childelse insert it as ys right childBegin
30、ing at the root, go down the tree and maintain: Pointer x : traces the downward path (current node) Pointer y : parent of x (“trailing pointer” ),Insert value 13,CS 477/677,38,Example: TREE-INSERT,x, y=NIL,Insert 13:,x = NIL y = 15,CS 477/677,39,Alg: TREE-INSERT(T, z),y NIL x root Twhile x NILdo y xif key z key xthen x left xelse x right xpz yif y = NILthen root T z Tree T was emptyelse if key z key ythen left y zelse right y z,Running time: O(h),CS 477/677,40,Readings,Chapter 6 Chapter 12,
