2

I have read about memory allocation for applications and I understand that, more or less, the heap, in memory, for a given application is dynamically allocated at the startup. However, there is also another concept called a min-heap, which is a data structure organized in the form of a tree where each parent node is smaller or equal to its children.

So, my question is: What are the relationships between the heap that is allocated at startup for a given application and the min-heap data structure that includes functions commonly referred to as 'heapify' and etc? Is there any relationship or is the min-heap data structure more of a higher level programming concept? If there is no relationship, is there any reason they've been given the same name?

This may seem like a silly question for some, but it has actually stirred up a debate at work.

Geoffrey Stocksdale Richards
  • 23
  • 3

1 Answers1

0

heap is a data structure which is actually a complete binary tree with some extra properties. There are 2 types of Heaps:

  1. MIN Heap
  2. MAX Heap

in min heap the root has the lowest value in the tree and when you pop out the root the next lowest element comes on the top. To convert a tree into heap we use heapify algorithm. It is also know as priority queue in c++. and usually as a competitive programmer we use STL function for heap so that we dont have to get into the hustle of creating a heap from scratch. Max heap is just the opposite with largest at the root. Usually heap is used because it has a O(logN) time complexity for removing and inserting elements and hence can even work with tight constraints like 10^6.

Now i can understand you confusion between heap in memory and heap data structure but they are completely different things. Heap in data structure is just a way to store the data.

Alphonse Prakash
  • 804
  • 7
  • 17