What is the most appropriate datastructure to implement priority queue?

Answer 1

Arrays are the most efficient data structure. Memory is allocated to the entire array as a single operation and the total memory consumed is equal to the product of the element size and the number of elements (all elements being of equal size, in bytes). This means that any element in the array can be accessed using simple pointer arithmetic from the start of the array, with the first element at offset 0. All high level languages hide the pointer arithmetic behind an array suffix operator, such that element [5] will be found 5 * sizeof (element) bytes from the start address of the array (the address where element [0] resides). Multi-dimensional arrays are implemented as an array of arrays, such that a two-dimensional array is a one-dimensional array where every element is itself a one-dimensional array. These can be thought of as being a table of rows and columns where the first dimension access a one-dimensional row array, and the second dimension accesses the column within that row. A three-dimensional array can then be thought of as being an array of tables or a cuboid (a stack of tables). A four-dimensional array can therefore be thought of as being an array of cuboids, a table of tables, or a cuboid of arrays. By imagining arrays in this manner it becomes much simpler to imagine arrays with more than 3 dimensions.

By contrast, a list or a tree structure is less efficient because every element requires at least one additional field to maintain the link from that element to another element, thus defining the structure. You also need to maintain an additional field to refer to the first element in the structure. If you have a structure that can dramatically vary in size, lists may be more efficient because there is no need to reallocate the entire structure; you simply allocate and deallocate memory for individual elements and update the links between elements to maintain the structure. However, you lose constant-time random access because you have to traverse the links in the structure to locate an individual element and the additional level of indirection means it will be slower than an array. However, reallocating an array often means copying the array to new memory. One way to minimise reallocations is to reserve more memory than you actually need, thus allowing you to add new elements more quickly at the cost of some memory. You only need to reallocate when you run out of reserve. You can also minimise the cost of reallocation by storing pointers rather than objects in your array. This adds an extra level of indirection, but speeds up the reallocation process by only copying pointers rather than objects being pointed.

Answer 2

The key characteristic of a priority queue is that elements in the queue must be ordered in some way, such that elements with higher priority move to the front of the queue more quickly than those with lower priority. As such, the most appropriate data structure for a priority queue is a heap, yielding O(1) extraction time and O(log n) insertion time.

Answer 3

Storage classes are not intended for efficiency, they are storage duration specifiers intended to define or refine the scope, visibility and lifetime of a variable.

Answer 4

struct

Answer 5

Heap