Questions tagged [heap-sort]

A comparison-based sorting algorithm based on Binary Heap data structure, heapsort works by visualizing the given elements as a special kind of complete binary tree called a heap!

33 questions
Filter by
Sorted by
Tagged with
76 views

Is it possible to sort this type of array in O(n) time?

Pseudo-Sorted array is an array that for every 0=<k<n the k smallest cell will be in the first 2k cells. For example the smallest cell will be in indexes 0-1 The second will be in indexes 0-3 ...
1 vote
934 views

Time complexity to remove an item from the heap

Given an array of size $n$ that has the item of the heap. To remove an arbitrary element from the heap we would need $O(n)$ to find the element and then $O(logn)$ to reheapify if I am commrect, which ...
• 515
90 views

Idea for Improving Heapsort

i have an idea of enhancing the heapsort by finding the max and min simultaneously and then swapping the max into the last node, and then the min will be swapped into the second to the last node, and ...
173 views

Heap sort worst case

I am really confused about this. I am trying to prove that the worst case of heap sort is Ω(nlogn) but i don't even know how to start.
450 views

Complexity of sorting $k$-sorted array using QuickSort and HeapSort

Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is ...
• 515
1 vote
3k views

How is the reccurence of Max Heapify T(n)= T(2n/3) + $\theta(1)$?

I'm trying to figure out how is the recurrence of $maxheapify()$ is $T(n)=T(2n/3)+O(1)$ If size of max heap is $n$, then calling $maxheapify(A, 1)$ will (at worst case) go through only one element in ...
• 109
1 vote
1k views

Running time of heap sort, when all number are identical

Given n numbers that all are identical, then what would be the running time of heap sort? Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?
1 vote
2k views

Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$ ...
• 11
911 views

How to derive the worst case time complexity of Heapify algorithm?

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure. I am asking this question in the light of the book "Fundamentals of Computer Algorithms&...
1 vote
2k views

prove that in binary heap buildheap function does at most 2N-2 comparison

prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks. buildheap procedure: we have n element and we build a heap at ...
• 21
95 views

Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

I recently came across the question: Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap. I looked for some solutions and found this one: Binary heap: ...
1 vote
93 views

What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
1 vote
534 views

What is the difference in time-complexity for sorting these 2-d arrays?

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements. It is given that each row is sorted in ascending order, Can you sort ...
• 83
220 views

Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

I have a min heap. I need to find the 7'th biggest value in the heap with $O(1)$. I need to build the algorithm. I dont realy have an idea how to get to this efficiency. Help? Thanks.
• 153
79 views

468 views

Please provide me a solution of Max-Heapify using Recursion Tree

I tried my best to solve the recurrence relation. $T(n) \le T(2n/3) + \Theta(1)$ Using the recursion tree. I could reach out the boundary condition when at depth ...
261 views

Are comparison sort algos appropriate for SUBJECTIVE sorting?

I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
• 143
1 vote
3k views

Worst case time complexity of heap sort

I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows: ...
• 111
2k views

Find K largest elements using a priority queue [duplicate]

Say we have a Priority Queue of size 1000 that is implemented using Max Heap. Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of ...
• 101
1k views

• 573
1 vote
215 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
1 vote