I have to build an indirect heap for a project, and I don't quite understand what it means. If you're building a heap out of an array, is implementing indirection simply adding some sort of map data structure to associate each item with its index? Or is it more complicated than that?
An indirect heap is a heap in which the data items stored are indexes into a list, array, or other data structure that holds the actual items.
Imagine that you have a list of names: ["jim","joe","bob","sam","susan","kelly","jessica"] from which you want to build a heap. A direct heap would have:
bob
joe jessica
sam susan jim kelly
An indirect heap would replace the names in the heap with indexes into the list:
2
1 6
3 4 0 5
Your comparison functions have to change. Rather than comparing heap[0] with heap[1], you end up comparing list[heap[0]] with list[heap[1]].
Some people call that a semi-indirect heap. A direct heap, in their parlance, contains an additional mapping from the name to the index.