DOC PREVIEW
Berkeley COMPSCI 61B - Lecture Notes

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 61B Data Structures and Programming MethodologyHash Tables and Binary Search TreesBinary Search TreeWhat if we are only interested the smallest or largest element ?Priority QueuesMain OperationsBinary Heapsmax()insert()Slide 10removeMax()Storing Binary HeapremoveMax()Running TimesBottom-Up Heap ConstructionExampleCost of Bottom Up ConstructionOther Types of HeapsReadingCS 61B Data Structures and Programming Methodology July 22, 2008David SunHash Tables and Binary Search Trees•A dictionary is used to look up arbitrary <key, value> pairs, given a specific key to search–With a good hash code and compression function we can do look up in constant time. –But there is no notion of priority or ordering among the keys so to find the smallest/largest element you will need to compare all the elements.Binary Search Tree•A binary search tree stores <key, value> pairs with a notion of order:–Looking up an arbitrary element may be slower, but we can perform query based searches.–What’s the smallest element in the tree?–What’s the largest element in the tree?–These operations are O(logN) where N is the number of elements.What if we are only interested the smallest or largest element ?Priority Queues•A priority queue is used to prioritize entries. –Just like binary search tree a total order is defined on the keys.–But you can identify or remove the entry whose key is the largest (or the smallest) in O(1) time.•Application:–Schedule jobs on a shared computer. The priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted, the highest priority job is selected from those pending.Main Operations•insert: adds and entry to the priority queue.•max: returns the entry associated with the maximum key (without removing it).•removeMax: removes and returns the entry associated with the maximum key. public interface PriorityQueue { public int size(); public boolean isEmpty(); Entry insert(Object k, Object v); Entry max(); Entry removeMax(); }Binary Heaps•A Binary Heap is a binary tree, with two additional properties–Shape Property: It is a complete binary tree – a binary tree in which every row is full, except possibly the bottom row, which is filled from left to right.–Heap Property (or Heap Order Property): No child has a key greater than its parent's key. This property is applied recursively: any subtree of a binary heap is also a binary heap.•If we use the notion of smaller than in the Heap Property we get a min-heap. We’ll look at max-heap in this class.max()•Trivial: The heap-order property ensures that the entry with the maximum key is always at the top of the heap. Hence, we simply return the entry at the root node. –If the heap is empty, return null or throw an exception.•Runs in Theta(1) time.insert()Let x be the new entry (k, v). 1. Place the new entry x in the bottom level of the tree, at the first free spot from the left. If the bottom level is full, start a new level with x at the far left. 2. If the new entry's key violates the heap-order property then compare x's key with its parent's key; if x's key is larger, we exchange x with its paren. Repeat the procedure with x's new parent. OriginalDashed boxes show where the heap property violatedRe-heapify upInserting <8,v>insert()Inserting <18,v>What’s the time complexity of insert?removeMax() 1. If the heap is empty, return null or throw an exception. 2. Otherwise, remove the entry at the root node. Replace the root with the last entry in the tree x, so that the tree is still complete.3. If the root violates the heap property then compare x with it’s children, swap x with the child with the larger key, repeat until x is greater than or equal to its children or reach a leaf.Starting Replace rootRe-heapify downFinalStoring Binary Heap•Since heaps are complete, one can use arrays for a compact representation •No node needs to store explicit references to its parent or children–If a node's index is i, its children's indices are 2i and 2i+1, and its parent's index is floor(i/2).removeMax()Starting Replace rootRe-heapify downFinalRunning Times•We could use a list or array, sorted or unsorted, to implement a priority queue. The following table shows running times for different implementations, with n entries in the queue.Binary Heap Sorted List/Array Unsorted List/Arraymax Theta(1) Theta(1) Theta(n)insert (worst-cast) Theta(log n)* Theta(n) Theta(1)*insert(best-case) Theta(1)* it depends Theta(1)*removeMax (worst) Theta(log n) Theta(1) Theta(n)removeMax (best) Theta(1) Theta(1) Theta(n)* If you are using an array-based data structure, these running times assume that you don’t run of room. If you do, it will take Omega(n) time to allocate a larger array and copy them into it.Bottom-Up Heap Construction•Suppose we are given a bunch of randomly ordered entries, and want to make a heap out of them. •What’s the obvious way–Apply insert to each item in O(n log n) time.•A better way: bottomUpHeap()1.Make a complete tree out of the entries, in any random order.2.Start from the last internal node (non-leaf node), in reverse order of the level order traversal, heapify down the heap as in removeMax().Example74 95 3 5 174 95 3 5 174 95 3 5 175 94 3 5 195 74 3 5 1Why this works? We can argue inductively:1. The leaf nodes satisfy the heap order property vacuously (they have no children).2. Before we bubble an entry down, we know that its two child subtrees must be heaps. Hence, by bubbling the entry down, we create a larger heap rooted at the node where that entry started.Cost of Bottom Up Construction•If each internal node bubbles all the way down, then the running time is proportional to the sum of the heights of all the nodes in the tree. •Turns out this sum is less than n, where n is the number of entries being coalesced into a heap. •Hence, the running time is in O(n), which is better than inserting n entries into a heap individually.Other Types of Heaps•Binary Heap is not the only implementation of a priority queue, other heaps also exist.•Several important variants are called "mergeable heaps", because it is relatively fast to combine two mergeable heaps together into a single mergeable heap. •The best-known mergeable heaps are called "binomial heaps," "Fibonacci heaps," "skew heaps," and "pairing heaps.“•We will not examine these in CS61B, but it’s good to know that they


View Full Document

Berkeley COMPSCI 61B - Lecture Notes

Documents in this Course
Lab

Lab

4 pages

Matrix

Matrix

3 pages

Numbers

Numbers

14 pages

Lectures

Lectures

12 pages

Project 1

Project 1

24 pages

Exam

Exam

8 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?