Skip to content

Clarify the priority queue mappings #476

@wojtask

Description

@wojtask

I can't really understand why we need the mapping mechanism between application objects and their corresponding indices in the heap array in the priority queue implementation. On page 174 it is mentioned that in the heap in this implementation contains pointers to the objects, instead of keys, as it was in previous sections of Chapter 6. Pointers are enough to set up such mapping – the heap can now determine which object occupies which index, and comparisons are done via object's keys. Objects shouldn't care about their placement in any data structure. This is an implementation detail, and any interaction with data structures should be done via their interface (the list of operations it specifies).

For now in #16 I am going to commit the implementation of priority queues that uses the mapping mechanism.

But soon I am going to send the above doubts to the Authors of the book, hoping to get some additional insights.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions