Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
expand_more
expand_more
format_list_bulleted
Question
Chapter 6.4, Problem 3E
Program Plan Intro
To determine the running time of heap sort on an array that is sorted in increasing order. Also, determine for decreasing order.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Heap is used to implement the priorityqueue. Revise the implementation using a sorted array list to store the elementsand name the new class PriorityUsingSortedArrayList. The elements inthe array list are sorted in increasing order of their priority with the last elementhaving the highest priority. Write a test program that generates 5 million integersand enqueues them to the priority and dequeues from the queue. Use the samenumbers for MyPriorityQueue and PriorityUsingSortedArrayList anddisplay their execution times.
suppose we are maintaining a collection of C elements such that, each time we add a new element to the collection, we copy the contents of C into a new array list of just the right size. What is the running time of adding n elements to an initially empty collection C in this case?
Given a singly linked list, print reverse of it using a recursive function
printLinkedList( node *first ) where first is the pointer pointing to the first data
node. For example, if the given linked list is 1->2->3->4, then output should be:
4 3 2 1
(note the whitespace in between each data value)
Chapter 6 Solutions
Introduction to Algorithms
Ch. 6.1 - Prob. 1ECh. 6.1 - Prob. 2ECh. 6.1 - Prob. 3ECh. 6.1 - Prob. 4ECh. 6.1 - Prob. 5ECh. 6.1 - Prob. 6ECh. 6.1 - Prob. 7ECh. 6.2 - Prob. 1ECh. 6.2 - Prob. 2ECh. 6.2 - Prob. 3E
Ch. 6.2 - Prob. 4ECh. 6.2 - Prob. 5ECh. 6.2 - Prob. 6ECh. 6.3 - Prob. 1ECh. 6.3 - Prob. 2ECh. 6.3 - Prob. 3ECh. 6.4 - Prob. 1ECh. 6.4 - Prob. 2ECh. 6.4 - Prob. 3ECh. 6.4 - Prob. 4ECh. 6.4 - Prob. 5ECh. 6.5 - Prob. 1ECh. 6.5 - Prob. 2ECh. 6.5 - Prob. 3ECh. 6.5 - Prob. 4ECh. 6.5 - Prob. 5ECh. 6.5 - Prob. 6ECh. 6.5 - Prob. 7ECh. 6.5 - Prob. 8ECh. 6.5 - Prob. 9ECh. 6 - Prob. 1PCh. 6 - Prob. 2PCh. 6 - Prob. 3P
Knowledge Booster
Similar questions
- an application has a huge number of find the maximum operations, but a relatively small number of insert and remove the maximum operations. Which priority- queue implementation do you think would be most effective: heap, unordered array, or ordered array? Explain your Answer.arrow_forwardImplement a Double Array Queue and test it for a very large case (100,000 randomly decided operations of enqueue or dequeue) Your program should compute the number of costly operations and cheap operations Your program should also ask the user about the ratio between enqueue and dequeue operations: The probability of enqueues and dequeues should never be of less than half the other (34% enqueues - 66% dequeues or 66% enqueues - 34% dequeues)arrow_forwardLet us assume that we have an application that performs many retrievals on a table, but few insertions and deletions. We do not know the size of the table. Which implementation is more appropriate for this application? a sorted array-based implementation an unsorted array-based implementation a binary search tree implementationarrow_forward
- In Java please Write a method to measure sortedness of a collection of linked nodes that hold Comparable data. Try to write solution in recursive instead of iterative. This is the method header: public static double sortedness(Node<Comparable> node)arrow_forwardGiven the following non-recursive implementation of depth-first search: A. Complete the implementation of depth-first search by filling in the TODO sections with the appropriate C++ code. Remember to: Print out each node you visit. Visit each node exactly once. B. What is the purpose of stack<string> q? C. What is the purpose of set<string> v?arrow_forwardConsider an input array A of size n in which n − 1 of the elements have identical values and the remaining one value is smaller than the n − 1 identical values. What is the running time of Heapsort with input A?arrow_forward
- Continuing on from your implementation of the PriorityQueue class, add the method create_heap_fast (self, values) which takes a Python list as a parameter. This method should put elements from the Python list into the priority queue without using the insert method. The Big-O of this method is O(n). The method should do the following: • Insert each element from the parameter list and append it to the binary heap. • Set the size to the number of elements in the parameter list. • Get the starting index position (i.e. last element which has a child, size // 2). • Rearrange the elements starting from the above index position by calling the percolate_down() method. • Keep rearranging and working backwards towards the root. Note: submit the entire class definition. You can assume that the parameter list is not empty. For example: Test pq PriorityQueue () keys [9, 5, 8, 6, 3, 2] pq.create_heap_fast(keys) = = print (pq) Result [0, 2, 3, 8, 6, 5, 9]arrow_forwardfor python HeapDelete(A,i) is an operation used to delete the item in node i from heap A. Describe the pseudocode of HeapDelete(A,i) that runs in O(log n) time for an n-element maxheap. Assume that HeapChangeKey(·, ·, ·) and Heapify(·, ·). you can call these operations in the developed HeapDelete(A,i).arrow_forwardIn C++, Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 20 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in the blank, etc ( Like prior program done with LISTS ) Create a class called Node: Have a Name and Priority. Data set - 1 is the highest priority, 10 is lowest priority. Enqueue and dequeue in the following order. Function Name, Priority Enqueue Joe, 3 Enqueue Fred, 1 Enqueue Tuyet, 9 Enqueue Jose, 6 Dequeue Enqueue Jing, 2 Enqueue Xi, 5 Enqueue Moe, 3 Dequeue Enqueue Miko, 7 Enqueue Vlady, 8 Enqueue Frank, 9 Enqueue Anny, 3 Dequeue Enqueue Xi, 2 Enqueue Wali, 2 Enqueue Laschec, 6 Enqueue Xerrax, 8 Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue Dequeue…arrow_forward
- How does a link-based implementation of the List differ from an array-based implementation? Select one: a. All of these b. A link-based implementation does not need to shift entries over to make room when adding a new entry to the List c. A link-based implementation is sized dynamically so it takes up only the memory to hold the current entries d. A link-based implementation does not need to shift entries up to remove a gap when removing an entry from the Listarrow_forwardplease do what is says Given a string representing an array/vector/linked-list (your choice, will use array for clarity moving forward) of integers both positive and negative, output all the negative values on the left-hand side of the array and all positive numbers on the right-hand side of the array while maintaining their relative positions. You must do this in linear time and linear space complexity or better, i.e. you cannot scan the entire list multiple times again and again to place the values in an new array. You MUST utilize methods related to QuickSort to receive credit for this problem. We will NOT accept iterative solutions. NOTE: Do NOT sort the array, the elements need to remain in their original relative order. Hint: take a look at the partition function in QuickSort. Case 1: Input 3: 1 -1 2 -2 3 -3 4 -4 5 -5 Output 3: -1 -2-3-4 -5 1 2 3 4 5 Case 2: Input 2: 14 9 -12 -13 -11 4 -4 3 3 9 Output 2: -12 -13 -11…arrow_forwardIn Java and C++ create a Generic ArrayList where all elements in the ArrayList must be of the same type. In every node of the linked list the size of the array it contains must be at least double the size of the previous node’s array. Between O(1) time and O(n) time. add(int index, E e) clear() contains(E e) ensureCapacity(int minCapacity) isEmpty() get(int index) remove(int index) size()arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education