DATA STRUCTURE: 1. Design and write, in pseudocode, an algorithm that, given a s
ID: 3687426 • Letter: D
Question
DATA STRUCTURE:
1. Design and write, in pseudocode, an algorithm that, given a simple undirected graph G = (V,E) and a single edge (u, v), will find the length of the cycle with the smallest number of edges
that includes the edge (u, v).
2. Write an algorithm in pseudocode that, given a reference for a node in a heap (being used as a minimization priority queue with integer priority keys) and an integer k, will subtract k from the
key of the node and adjust the heap appropriately.
You can assume that the heap is stored in an array.
3. (a) Describe how to implement a heap using an array.
(b) Describe the pseudo code of the in-place heap sort algorithm, and analyze its time complexity.
Explanation / Answer
2) Deleting a Value From a Heap
3) Save the value, X, in the rightmost node in the bottom level then delete this node.
4. Put X into the node containing K and then SHIFT X UP, if it is smaller than its parent, or SHIFT it DOWN if it is larger than either of its children.
3.,a) A heap is a binary tree that has special structure compared to a general binary tree that the root is greater than any value in a subtree
3(b) Heap sort algorithm is divided into two basic parts : Creating a Heap of the unsorted list. Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.
The steps of the heap sort algorithm are:
You repeat steps 2 & 3 until you finish all the data.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.