Minheap/Maxheap

#1

let’s say we want top ten elements in an array,if we apply heap we get them but the output need not be in sorted order right?

#2

@dare_devil_007 in min heap if you keep popping elements from top output will be sorted in asc. its the property of min heap;
i hope its clear if yes dont forget to hit like and mark resolved :smiley:

#3

#include<bits/stdc++.h>
using namespace std;
//minHeap
//O(NlogN)

void buildHeap(std::vector &v) {

for (int i = 2; i < v.size(); i++) {

	int idx = i;
	int parent = i / 2;


	while (idx > 1 and v[idx] < v[parent]) {

		swap(v[idx], v[parent]);

		idx = parent;
		parent /= 2;

	}
}

}

int main() {

std::vector<int> v{ -1, 10, 30, 4, 56, 9, 73};
buildHeap(v);


for (auto x : v) {

	cout << x << " ";

}
return 0;

}
for the above input i am getting output as
4 9 10 56 30 73

#4

@dare_devil_007 yes you are right i misunderstood your question.
o/p need not to be in sorted order as you are just building the heap.
o/p comes in sorted order when you reheapify the heap after displaying the topmost element

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.