The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
130 views

This question is in CLRS,if we have a max heap it is always in sorted order(descending) order.And by extension if we have min heap the array is sorted in ascending order.Is this true?

I have a counter example for 100,50,20,1,3,10,5,this satisfied max-heap property but is not sorted when represented as an array.

Edit 1: Is it required always Heapify the heap,when we represent it as an array is it an heapified representation or not?

If we heapify after deletion and store max deleted element then we get sorted array.

asked in DS by Active (1.5k points)
edited by | 130 views
0

Is it required always Heapify the heap,when we represent it as an array is it an heapified representation or not?

It has to be a heapified, else how can you state that the given data structure is a Heap. For a data structure to be classified as a Heap, it must satisfy the properties of a Heap. So, if the Heap doesn't follow th properties of a heap, it  has to be heapified. 

 

If we heapify after deletion and store max deleted element then we get sorted array.

You get the sorted array once you've done deletion of Max element form the heap and applied heapify   n/2 no. of times( n being the length of array to be sorted).

This question is in CLRS,if we have a max heap it is always in sorted order(descending) order.And by extension if we have min heap the array is sorted in ascending order.Is this true?

Can you state the page no. where this is written.

0
It is a exercise question it is not stated its a question from exercise 6.1 I think don't know exact question.CLRS doesn't have solutions to check answers hence asked.
0

Actual statements are the reverse of what you have written.

If elements of an array is in descending order , then it will be a max heap.

If elements of an array is in ascending order , then it will be a min heap.

0
I have written the same thing max heap is descending and min heap is ascending.
0

You've yourself given the answer by quoting this counter example: (100,50,20,1,3,10,5). Even though this represents a max heap, but the array is not sorted.  Same goes with min heap also.

0
That is the array representation and it is not a heap as it is not being heapified if heapified then we get 100,50,20,10,5,3,1 which is sorted order.I just wanted to know if heapify is must even if not stated but then you mentioned that heap should always maintain heap property,after insertion or deletion.
0
I am actually confused so what is the answer :p
+1

sripo No there is a difference between p→q and q →p. I hope you have read that in mathematical logic 

+1
An array representation of a max heap is not necessarily sorted in descending order

Similarly an array representation of a min heap is not necessarily sorted in ascending order.
0
Simple and Sleek.
0
I liked your intuition how do you connect all the concepts?

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
183,548 comments
68,742 users