Dated: Jan 16, 12
Graded Discussion Board (GDB) will be launched on 19th January and it will remain open for two days.
The topic for GDB is:
“Is heap an implicit data structure for Priority queue? yes or no justify. “
A concise, coherent and to-the-point comment is preferred over lengthy comment having irrelevant details.
Comments posted on regular Lesson's MDB or sent through e-mail will NOT be considered.
No. A priority queue is an abstract data structure, independent of how the data is organized. A priority queue can be implemented as an unordered list, a sorted list, a linked list, etc. Some better than others in their support of the priority queue operations, depending on the characteristics of the data to be managed. A heap happens to be a good data structure for an efficient implementation of a priority queue.
no it's explicit...I'm not sure what you mean by implicit.
It's explicit in the fact that it explicitly describes a way to implement a priority queue.
However, it's implicit if you look at a heap as its own data structure, which by the way it's constructed implies a priority queue.
These are words and as a computer scientist I hate the English language for its imprecision, so what kind of question is this? (and I'm assuming it's part of an assignment, because no one in their right mind would ask a question like this...so my point is that it's a stupid question for your assignment, sorry you have stupid teachers)
...and unfortunately questions like these are systemic problems.
Unfortunately, your extra details (as provided from your professor) do NOT shed any light on the meaning of implicit vs. explicit. How can a man-made structure be "natural" (i.e. somebody thought of the idea for a heap). So unfortunately I'm going to try to re-answer given your extra details and it's going to end up being the same response as I gave above:
There are two ways to interpret a heap:
1) Implicitly: the heap is a data structure which is a nearly balanced tree structure (actually it's as closed to being balanced as can be achieved). The balanced tree is constructed in such a way, that every node in the tree is smaller (or greater for a max heap) than ALL of its descendants. In this way, a heap represents an implicit priority queue. That is, given the conditions for a heap, it will represent a priority queue.
2) Explicitly: now think about how you would actually IMPLEMENT a heap. By say an array structure (which is a "natural" choice since the heap should be a nearly balanced tree, meaning that an array structure will result in a small amount of wasted space...minuscule compared to the size of the heap). The rules for implementing a heap must satisfy the above definition FOR a heap.
So the question here, is whether or not a Heap is an abstract data type. If you think of it as an abstract data type, then YES it implicitly implements a priority queue. If instead you think of a heap as a CONCRETE data type (i.e. an array implementation of a heap), then by way of the construction you are explicitly creating a priority queue.
I suspect that the answer the professor wants, is that it IS an implicit implementation of a priority queue. This is because if you DO implement the heap as say an array of elements, then it's ALWAYS the case the highest priority (whether it be the minimum or maximum value) is ALWAYS at the HEAD of the array and thus popping off of the head of the array ALWAYS results in the highest priority item being removed.
I just don't really like this question because if you think of a heap as an abstract data type then saying that it's implicitly a priority queue is somewhat circular reasoning (because you have defined the "heap" structure as a priority queue, so of COURSE it's a priority queue).
To try and make this concrete, let's construct a DIFFERENT data structure which is a priority queue...a SIMPLE structure:
We will have an array of elements. We will maintain this structure such that the minimum (or maximum) value is ALWAYS at the first element. So when you add the first value it will be trivially the minimum (or maximum). Then when you add subsequent values you merely see if this value is less than (or greater than) the head, if it's not then just add it to the end of the array. When you remove an element, you merely search through the entire array and find the new minimum and move that minimum element to the head of the array (and do whatever cleanup you have to such that the array remains contiguous).
So is what I described above an EXPLICIT or IMPLICIT implementation of a priority queue? I would think you would say it's a EXPLICIT implementation.
But just like I created rules for the above implementation, there would be rules (and there ARE rules) for the heap. There are rules for how to maintain the heap data structure using the heapify operations. So once we actually IMPLEMENT the heap, it becomes an explicit priority queue because we EXPLICITLY define rules such that the priority queue condition is maintained.
What we are talking about here is semantics of the english language and such semantics have no PLACE in Computer Science, which is one of the things that irritates me about the way Computer Science is taught. When you run a program, you think of it on a VERY HIGH level, i.e. objects and functions etc. However, as far as the computer is concerned, you are merely feeding the CPU 1's and 0's and it is responding to those 1's and 0's in some predetermined way. The reality of your program IS THE ONES and ZEROS, NOT your high level program!
A Heap is a data structure that provides an efficient implementation of priority queue operations. That is, it provides a - first in largest out - queue, according to some ordering relation. In more detail, a priority queue provides at least the following queue operations
• Insert element into queue.
• Extract largest element from queue.
This minimal set of primordial is often extended by an Adjust Key operation which adjusts the key of an element already in the queue, and a non destructive version of Extract hatchet which returns the largest element in the queue without removing it from the queue.
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. 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 cluster of people with sticky notes and the next person's phone number.
A heap happens to be a good data structure for an efficient implementation of a priority queue. In computer science, an implicit data structure is a data structure that uses very little memory besides the actual data elements.