My data structure needs three operations:
The existing code is a single-linked list and does a linear search to find an insert point. O(n).
Finding and removing the smallest element is trivial: pull off and dispose of the head link. O(1).
The insert returns a pointer to the link, and the delete call gets that pointer. Were it a double-linked list the link could simply be deleted. O(1). Alas the list is single-linked, and the list is searched for the node of this address, so it's O(n). This search is expensive, but it does allow detection of an attempt to remove a node twice in some cases: attempted deletion of a node simply not on the list won't find it so won't do anything except generate a warning in the log. On the other hand the nodes are stored in a LIFO memory pool, so are likely to be reused, so an accidental re-deletion of a node may well remove some other node instead.)
OK, with a heap, the insert is O(log n). Delete of minimum is O(log n). Both simple.
But what of delete-by-key? If I keep the heap in an array, it's basically a linear search, O(n). I move the elements around in the heap to keep the heap property (bubbling down and up as needed), so I can't just use the node's address. Plus, unless you accept a fixed maximum size, you need to reallocate the array which typically moves it.
I'm thinking maybe the heap could be an array of POINTERS to the actual nodes, which live elsewhere. Each node would have it's array index in it, and as I move pointers-to-nodes around in the heap, I'd update the node with its new array index. Thus a request to delete a node could supply me with the node. I use the node's stored index into the heap, and delete that pointer, so now log(N). It just seems far more complicated.
Given the extra overhead of allocating non-moving nodes separately, and keeping their array index field updated, sounds like it might be more than some very occasional number of linear searches. OTOH, an advantage of keeping nodes separate from the array heap is that it's faster to swap pointers than whole nodes (which in my case may be 32 bytes or more).
Any simpler ideas?
The data nodes are allocated upon queuing, deallocated upon dequeue, and not moved. When you queue data, your return value is this node's address, though to keep the API clean the return value's type is opaque.
The heap is a heap of pointers to these nodes.
The data nodes have an unsigned int which holds the current array offset of the pointer to them.
When we move the pointer (due to a heap operation such as insert or delete) we update it's nodes index. For instance, if we determine our key is higher priority than our parent, we move our parent to our current position like this:
apnode[i] = apnode[iParent];
apnode[i]->iOffset = i;
Inserts of data with any key, and Deletes of node with highest-priority key, work normally. Both are O( log n ).
The new operation, to delete a node that is not yet highest-priority, involves casting the opaque key back to a pointer, dereferencing to get the corresponding pointer's current offset, then deleting that. Thus, getting to the pointer to delete is a very fast O(1). At that point, deleting it normally is the usual O( log n ).
The extra overhead to support this random delete amounts to setting that offset. It's only one line of code but on the other hand substantially increases the set of cache lines touched, compared to a pointer heap without this feature. On the other hand, the heap is probably substantially faster for being a pointer heap than actually having the array elements be the nodes themselves.
Almost totally off-topic but very useful for anyone reading this:
All textbooks seem to present heap operations as follows: add your item to the end of the heap, then do swaps to heapify it down to where it belongs. Each of those swaps is three instructions, though. It's more efficient to instead consider a pointer to the end of the heap as the candidate destination (CD) for the new data, but not write it there yet.
Then, compare the new data's key with the parent. If the new data is lower or equal priority, write it at CD and done. Otherwise, simply copy the parent to CD, and parent's address becomes new CD. Repeat. This cuts the actual data moves by 2/3rds.