My question might seem childish but I really don't understand this question as I am just a newbie to data structures course. I do know how max and min heap work, but I am not sure that whether heap is implicit data structure to implement priority queue.
1 Answers
5
votes
Wikipedia is back up :D
From the article:
In computer science, an implicit data structure is a data structure that uses very little memory besides the actual data elements...
So yes, a heap would fit the bill because it can be implemented as a simple array. A heap that is implementing a priority queue would be an implicit data structure, but not because it's implementing a priority queue. It's because heaps don't use anything special to keep track of its elements, only the array location.
Also, I completely disagree with your friend's interpretation. There is no "natural" data structure for any problem, only ones that happen to be very convenient under the circumstances.
Computing and data structures are abstract ideas that can be implemented in many different ways. A linked list can be implemented on the heap, on the hard drive, over the internet, and in the form of a bunch of people with sticky notes and the next person's phone number. Calling the whole set of them a "natural" data structure to use for some particular problem is wrong.
