Priority task executor with duplicate task ids

Implement an executor that accepts tasks, each with an id and a priority, and runs them highest priority first. The same task id can be submitted more than once. Decide and implement what that means (replace, ignore, or run again) and support cancelling a task by id.

Discuss the data structures, the cost of each operation, and how you would make it safe for several threads.