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!

Filter by
Sorted by
Tagged with
0 votes
0 answers
32 views

Why is the time complexity of introspective sort O(n log n)?

I understand that intro sorts avoids the running time O(n^2) of quick sort, by changing to heap sort when the algorithm exceeds a certain recursion depth. But what about insertion sort? It kicks in ...
user avatar
0 votes
0 answers
21 views

Why the last elements of the array of heap is itself heap

If we represent a heap using array the 2nd half of the array will be represent the leaf nodes of the heap. But I can not understand for array of length n, all elements in range A[[n/2+1]....n] are ...
user avatar
  • 171
0 votes
2 answers
142 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 ...
user avatar
  • 459
0 votes
1 answer
219 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 ...
user avatar
  • 51
1 vote
1 answer
390 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)$?
user avatar
1 vote
2 answers
919 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)$ ...
user avatar
  • 11
0 votes
1 answer
500 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&...
user avatar
1 vote
1 answer
480 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 ...
user avatar
  • 13
0 votes
1 answer
63 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: ...
user avatar
1 vote
2 answers
60 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 ...
user avatar
1 vote
1 answer
305 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 ...
user avatar
  • 71
0 votes
2 answers
98 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.
user avatar
  • 153
2 votes
1 answer
57 views

How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved. Please help. The equation: $\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h)...
user avatar
1 vote
1 answer
140 views

Max heap and array relation

This question is about max heap and array Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at ...
user avatar
  • 133
0 votes
2 answers
1k views

is AVL tree is better than heap for sorting purpose?

for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?
user avatar
1 vote
2 answers
2k views

Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n

The Question of the CLRS $6.1-7$ exercise reads as: Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \...
user avatar
0 votes
1 answer
340 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 ...
user avatar
4 votes
1 answer
164 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 ...
user avatar
1 vote
2 answers
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: ...
user avatar
  • 111
0 votes
0 answers
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 ...
user avatar
  • 101
3 votes
0 answers
937 views

How to determine the fewest number of comparisons for Heapsort?

I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case. In its average case, Heapsort only requires $...
user avatar
0 votes
1 answer
860 views

Why is Heapsort in O(n log n) if not all n operations take time log n?

let's consider that we already have constructed heap array. so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap ...
user avatar
  • 235
0 votes
0 answers
647 views

How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...
user avatar
  • 135
0 votes
2 answers
2k views

Heap sort best case time - $\mathcal O(n)$?

It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ? The argument here is, If my input has all the same keys, then every time I delete the root, I do ...
user avatar
4 votes
2 answers
377 views

If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are ...
user avatar
0 votes
0 answers
81 views

Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed: $\\$ For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly. Step 1: From ...
user avatar
1 vote
1 answer
1k views

When the heapsort worst case occurs?

The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$. What are the worst-case inputs for heapsort?
user avatar
1 vote
1 answer
691 views

Does Heapsort work in time o(n log n) in the best case?

Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs? For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about ...
user avatar
  • 543
1 vote
0 answers
208 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 ...
user avatar
1 vote
1 answer
720 views

Lower bound on distinct element heapsort

I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS: Exercise 6.4-5 Show that when all elements are distinct, the best-case running time of heapsort ...
user avatar
1 vote
1 answer
2k views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
user avatar
  • 19