# 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!

30 questions
Filter by
Sorted by
Tagged with
18 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 ...
59 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 ...
69 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 ...
178 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)$?
512 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)$ ...
273 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&...
320 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 ...
55 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: ...
41 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 ...
211 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 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.
47 views

280 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 ...
138 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 ...
2k 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: ...
1k 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 ...
903 views

203 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 ...