Heap exercises in C Programming in C

• LEVEL 3 One dimensional array Sorting Sorting using heap-sort algorithm: Sort the elements of an array A in ascending order. Heapsort algorithm inserts all elements into a heap, then removes them from the root of a heap until the heap is empty. Sort can be done in place with the array to be sorted.Instead of deleting an e...
• LEVEL 3 kth largest elements in an array using a heap: Write a function that prints the \(k^{th}\) largest elements in an array. Elements in array can be in any order. For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., \(k\) = 3 then your program s...
• LEVEL 3 Check whether a given binary tree is a Max heap: Write a function that checks whether a given binary tree is a Max heap. A Binary tree need to fulfill the following two conditions for being a heap: It should be a complete tree (i.e. all levels except last should be full). Every node's value should ...
• LEVEL 3 Building a Max-heap by adding values and evaluating complexities: Let T be the following table:\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline3 & 5& 1 & 6 & 8 &11 &2 &4 & 9 & 10\\\hline\end{array}\) Build the Max-Heap. You should represent the heap obtained after the insertion of ea...
• LEVEL 3 Implement a stack using a heap: We are interested in this part to implement a $$\texttt{stack}$$ of integers using a $$\texttt{Max-Heap}$$. Let $$\texttt{H}$$ be a $$\texttt{Max-Heap}$$ allowing the following operations: $$\texttt{Max-Heap CreateHeap();}$$ This operation creates a ...
• LEVEL 3 Sorting Heapsort complexity: What is the asymptotic running time of the $$\texttt{heapsort}$$ algorithm on an array of length $$n$$ that is already sorted in ascending order? What about if the array is sorted in decreasing order? In both cases, justify your answer....
• LEVEL 3 Priority queue Priority Queue and Min heap: A min heap H is a binary tree having the following property:\ $\forall N \in H, \forall \ LN \in LEFT(N), \forall \ RN \in RIGHT(N), data(N) \leq data(LN) $ and $ data(N) \leq data(RN)$ Jobs arriving to a computer system for processing are given a pr...
• LEVEL 3 Binary heaps: A max-heap is a perfect binary tree in which data of each node is $$>$$ than those of its children (the root contains the max). Consider the following max-heap. **img**binaryheaps1.png##img## The max-heap above resulted after a sequence of $$\text...
• LEVEL 3 Recursive function Recursion Sorting Tracing QuickSort and Heapsort: Consider the following table: $$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline 9 & 15& 5 &7 &11 &4 &10 &13 &8\\\hline \end{array}$$ Trace $$\texttt{QuickSort}$$ using the above table to sort its entries. Trace $$\texttt{Heap...
• LEVEL 3 Recursive function Recursion Binary trees Domain inclusion of heaps: A min-heap is a complete binary tree where the value of each element is less than the values of its children, if any.  Remark: each value is unique in a heap (it can't be repeated). Define the data structure for dynamic implementation of a heap of i...
• LEVEL 3 Recursive function Recursion Heap of prime factors: An integer number is represented by a heap consisting of the number prime factors. Ex: the number 24 is represented by the heap below: **img**heapprimefactors.png##img## Given the function $$\texttt{void primeFactors(int n)}$$ that prints the prime ...
• LEVEL 3 Recursive function Recursion Min-max heaps: A $\texttt{Min-Max Heap}$ is a hybrid data structure between a $\texttt{Min Heap}$ and a $\texttt{Max Heap}$. More precisely, it is a perfect $\texttt{BT}$ in which: nodes on an even level are smaller than those of their descendants (direct or indir...
• LEVEL 3 Hash tables Hashing with heaps: Consider a hash table T[m] where separate chaining is used such that keys with the same hash value are stored in a heap (dynamically implemented). We assume the existence of a hash h, and that keys in the heap are of type t_Element, and that 2 keys c...

Back to the list of exercises