Data Structures - Stanford University

1 Data StructuresJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 Typical Quarter at Stanfordvoid quarter() {while(true) { // no break :(task x = GetNextTask(tasks);process(x);// new tasks may enter}} GetNextTask()decides the order of the tasks2 Deciding the Order of the Tasks Possible behaviors of GetNextTask(): Returns the newest task (stack) Returns the oldest task (queue) Returns the most urgent task (priority queue) Returns the easiest task (priority queue) GetNextTask()should run fast We do this by storing the tasks in a clever way3 OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)Fenwick TreeLowest Common Ancestor (LCA)Stack and Queue4 Stack Last in, first out (LIFO) Supports three constant-time operations Push(x): insertsxinto the stack Pop(): removes the newest item Top().)

2 Returns the newest item Very easy to implement using an arrayStack and Queue5 Stack Implementation Have a large enough arrays[]and a counterk, which startsat zero Push(x): sets[k] = xand incrementkby 1 Pop(): decrementkby 1 Top(): returnss[k - 1](error ifkis zero) C++ and Java have implementations of stack stack(C++),Stack(Java) But you should be able to implement it from scratchStack and Queue6 Queue First in, first out (FIFO) Supports three constant-time operations Enqueue(x): insertsxinto the queue Dequeue(): removes the oldest item Front(): returns the oldest item Implementation is similar to that of stackStack and Queue7 Queue Implementation Assume that you know the total number of elements thatenter the queue.

3 Which allows you to use an array for implementation Maintain two indicesheadandtail Dequeue()incrementshead Enqueue()incrementstail Use the value oftail - headto check emptiness You can usequeue(C++) andQueue(Java)Stack and Queue8 OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)Fenwick TreeLowest Common Ancestor (LCA)Heap and Priority Queue9 Priority Queue Each element in a PQ has a priority value Three operations: Insert(x, p): insertsxinto the PQ, whose priority isp RemoveTop(): removes the element with the highest priority Top(): returns the element with the highest priority All operations can be done quickly if implemented using aheap priority_queue(C++),PriorityQueue(Java)H eap and Priority Queue10 Heap Complete binary tree with the heap property.

4 The value of a node values of its children The root node has the maximum value Constant-timetop()operation Inserting/removing a node can be done inO(logn)timewithout breaking the heap property May need rearrangement of some nodesHeap and Priority Queue11 Heap ExampleFigure from WikipediaHeap and Priority Queue12 Indexing the Nodes Start from the root, number the nodes1,2, ..from left toright Given a nodekeasy to compute the indices of its parent andchildren Parent node: k/2 Children:2k,2k+ 1 Heap and Priority Queue13 Inserting a a new node in the last level, as far left as possible If the last level is full, make a new the new node breaks the heap property, swap with its parentnode The new node moves up the tree, which may introduceanother 2 until all conflicts are resolved Running time=tree height=O(logn)Heap and Priority Queue14 Implementation.

5 Node Insertion Inserting a new node with value v into a heap Hvoid InsertNode(int v) {H[++n] = v;for(int k = n; k > 1; k /= 2) {if(H[k] > H[k / 2])swap(H[k], H[k / 2]);else break;}}Heap and Priority Queue15 Deleting the Root the root, and bring the last node (rightmost node inthe last level) to the the root breaks the heap property, look at its children andswap it with the larger one Swapping can introduce another 2 until all conflicts are resolved Running time=O(logn) Exercise: implementation Some edge cases to considerHeap and Priority Queue16 OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)Fenwick TreeLowest Common Ancestor (LCA)Union-Find Structure17 Union-Find structure Used to store disjoint sets Can support two types of operations efficiently Find(x): returns the representative of the set thatxbelongs Union(x, y): merges two sets that containxandy Both operations can be done in (essentially) constant time Super-short implementation!

6 Union-Find Structure18 Union-Find structure Main idea: represent each set by a rooted tree Every node maintains a link to its parent A root node is the representative of the corresponding set Example: two sets{x,y,z}and{a,b,c,d}Union-Find Structure19 Implementation Idea Find(x): follow the links fromxuntil a node points itself This can takeO(n)time but we will make it faster Union(x, y): runFind(x)andFind(y)to findcorresponding root nodes and direct one to the otherUnion-Find Structure20 Implementation We will assume that the links are stored inL[]int Find(int x) {while(x !)}

7 = L[x]) x = L[x];return x;}void Union(int x, int y) {L[Find(x)] = Find(y);}Union-Find Structure21 Path Compression In a bad case, the trees can become too deep .. which slows down future operations Path compression makes the trees shallower every timeFind()is called We don t care how a tree looks like as long as the root staysthe same AfterFind(x)returns the root, backtrack toxand reroute allthe links to the rootUnion-Find Structure22 Path Compression Implementationsint Find(int x) {if(x == L[x]) return x;int root = Find(L[x]);L[x] = root;return root;}int Find(int x) {return x == L[x] ?

8 X : L[x] = Find(L[x]);}Union-Find Structure23 OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)Fenwick TreeLowest Common Ancestor (LCA)Binary Search Tree (BST)24 Binary Search Tree (BST) A binary tree with the following property: for each node , value ofv values inv s left subtree value ofv dvalues inv s right subtreeFigure from WikipediaBinary Search Tree (BST)25 What BSTs can do Supports three operations Insert(x): inserts a node with valuex Delete(x): deletes a node with valuex, if there is any Find(x).

9 Returns the node with valuex, if there is any Many extensions are possible Count(x): counts the number of nodes with value less than orequal tox GetNext(x): returns the smallest node with value xBinary Search Tree (BST)26 BSTs in Programming Contests Simple implementation cannot guarantee efficiency In worst case, tree height becomesn(which makes BSTuseless) GuaranteeingO(logn)running time per operation requiresbalancing of the tree (hard to implement) We will skip the implementation details Use the standard library implementations set,map(C++) TreeSet,TreeMap(Java)Binary Search Tree (BST)27 OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)

10 Fenwick TreeLowest Common Ancestor (LCA)Fenwick Tree28 Fenwick Tree A variant of segment trees Supports very useful interval operations Set(k, x): sets the value ofkth item equal tox Sum(k): computes the sum of items1, .. ,k(prefix sum) Note: sum of itemsi, .. ,j=Sum(j) Sum(i 1) Both operations can be done inO(logn)time usingO(n)spaceFenwick Tree29 Fenwick Tree structure Full binary tree with at leastnleaf nodes We will usen= 8for our example kth leaf node stores the value of itemk Each internal node stores the sum of values of its children , Red node storesitem[5]+item[6]Fenwick Tree30 Summing Consecutive Values Main idea.