Data Structures - Stanford University

← Back to document page

data StructuresJaehyun ParkCS 97SIStanford UniversityJune 29, 2015Typical Quarter at Stanfordvoid quarter() {while(true) { // no break :(task x = GetNextTask(tasks);process(x);// new tasks may enter}} GetNextTask()decides the order of the tasks2Deciding 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 way3OutlineStack and QueueHeap and Priority QueueUnion-Find StructureBinary Search Tree (BST)Fenwick TreeLowest Common Ancestor (LCA)Stack and Queue4Stack Last in, first out (LIFO) Supports three constant-time operations Push(x): insertsxinto the stack Pop(): removes the newest item Top(): returns the newest item Very easy to implement using an arrayStack and Queue5Stack Implementation Have a large enough arrays[]and a counterk, which startsat zero Push(x): sets[k] = xand incrementkby 1 Pop(): decrementkby 1 Top().)

Goal: preprocessing the tree in O(nlogn) time in order to answer each LCA query in O(logn) time Lowest Common Ancestor (LCA) 40. Preprocessing ... Data Structures Author: Jaehyun Park[3ex] CS 97SI Stanford University Created Date () ...

  Data, Preprocessing