想将链表升级为优先堆，但需要按值删除
want to upgrade a linked list to a priority heap, but I need delete by value
我的数据结构需要三个操作：
- 在排序中的随机位置插入一个元素
- 查找并移除最小元素
- （很少）通过插入时返回的某个键删除元素
现有代码是单linked 列表，并进行线性搜索以查找插入点。 O(n).
找到并移除最小的元素很简单：拉下并处理头部 link。 O(1).
插入 returns 指向 link 的指针，删除调用获取该指针。如果它是双重 linked 列表，则 link 可以简单地删除。 O（1）。唉，这个列表是单linked的，在列表中搜索这个地址的节点，所以是O(n)。这种搜索是昂贵的，但在某些情况下它确实允许检测两次删除节点的尝试：尝试删除一个根本不在列表中的节点不会找到它所以除了在日志中生成警告之外不会做任何事情.另一方面，节点存储在 LIFO 内存池中，因此很可能会被重用，因此意外重新删除一个节点可能会删除其他一些节点。）
OK，有了堆，插入是O(log n)。最小删除是O(log n)。都很简单。
但是按键删除呢？如果我将堆保存在一个数组中，它基本上是一个线性搜索，O(n)。我在堆中四处移动元素以保持堆 属性（根据需要上下冒泡），所以我不能只使用节点的地址。另外，除非您接受固定的最大大小，否则您需要重新分配通常会移动它的数组。
我在想也许堆可能是指向实际节点的指针数组，这些节点位于其他地方。每个节点都会有它的数组索引，当我在堆中移动指向节点的指针时，我会用它的新数组索引更新节点。因此，删除节点的请求可以为我提供该节点。我将节点的存储索引用于堆中，并删除该指针，所以现在是 log(N)。只是看起来要复杂得多。
鉴于单独分配非移动节点并保持其数组索引字段更新的额外开销，听起来可能比一些非常偶然的线性搜索要多。 OTOH，将节点与数组堆分开的一个优点是交换指针比整个节点更快（在我的例子中可能是 32 个字节或更多）。
有更简单的想法吗？
好的。
你可以留在记忆中：
- 您的数据结构，包含有效负载和优先级，动态分配。结构（指针）的地址是
removal key.
- 保留和维护二进制堆，包含
pointers这些数据结构。但是，heapify 元素根据优先级，包含在结构中，通过指针。
因此，您的算法：
插入：创建数据结构，将指针部署到堆，重新平衡堆：Log(N)
删除最后一个：从堆中取出最后一个元素，删除结构，从堆中删除最后一个元素，重新平衡堆：Log(N)。
删除随机元素：获取元素的指针，通过指针获得优先级，在堆中按优先级搜索此元素：Log(n)。删除结构，从堆中删除指针。重新平衡堆 - 再次 Log(N)。
数据节点在入队时分配，出队时释放，不移动。当你排队数据时，你的 return 值是这个节点的地址，尽管为了保持 API 干净，return 值的类型是不透明的。
堆是指向这些节点的指针的堆。
数据节点有一个无符号整数，它保存指向它们的指针的当前数组偏移量。
当我们移动指针（由于插入或删除等堆操作）时，我们更新它的节点索引。例如，如果我们确定我们的键比我们的父级优先级更高，我们将我们的父级移动到我们当前的位置，如下所示：
apnode[i] = apnode[iParent];
apnode[i]->iOffset = i;
插入任何键的数据，以及删除具有最高优先级键的节点，工作正常。两者都是 O( log n ).
删除尚未成为最高优先级的节点的新操作涉及将不透明键强制转换回指针，取消引用以获取相应指针的当前偏移量，然后将其删除。因此，到达要删除的指针的时间非常快 O(1)。此时，正常删除它是通常的 O( log n ).
支持此随机删除的额外开销相当于设置该偏移量。它只是一行代码，但另一方面，与没有此功能的指针堆相比，它大大增加了所触及的缓存行集。另一方面，作为指针堆的堆可能比实际将数组元素作为节点本身要快得多。
几乎完全跑题了，但对任何阅读本文的人都非常有用：
似乎所有的教科书都是这样介绍堆操作的：将您的项目添加到堆的末尾，然后进行交换以将其堆化到它所属的位置。不过，这些交换中的每一个都是三个指令。将指向堆末尾的指针视为新数据的候选目的地 (CD) 更有效，但还没有将其写入那里。
然后，将新数据的密钥与父数据进行比较。如果新数据的优先级较低或相同，则将其写入 CD 并完成。否则，只需复制 parent 到 CD，parent 的地址就成为新的 CD。重复。这将实际数据移动减少了 2/3。
我的数据结构需要三个操作：
- 在排序中的随机位置插入一个元素
- 查找并移除最小元素
- （很少）通过插入时返回的某个键删除元素
现有代码是单linked 列表，并进行线性搜索以查找插入点。 O(n).
找到并移除最小的元素很简单：拉下并处理头部 link。 O(1).
插入 returns 指向 link 的指针，删除调用获取该指针。如果它是双重 linked 列表，则 link 可以简单地删除。 O（1）。唉，这个列表是单linked的，在列表中搜索这个地址的节点，所以是O(n)。这种搜索是昂贵的，但在某些情况下它确实允许检测两次删除节点的尝试：尝试删除一个根本不在列表中的节点不会找到它所以除了在日志中生成警告之外不会做任何事情.另一方面，节点存储在 LIFO 内存池中，因此很可能会被重用，因此意外重新删除一个节点可能会删除其他一些节点。）
OK，有了堆，插入是O(log n)。最小删除是O(log n)。都很简单。
但是按键删除呢？如果我将堆保存在一个数组中，它基本上是一个线性搜索，O(n)。我在堆中四处移动元素以保持堆 属性（根据需要上下冒泡），所以我不能只使用节点的地址。另外，除非您接受固定的最大大小，否则您需要重新分配通常会移动它的数组。
我在想也许堆可能是指向实际节点的指针数组，这些节点位于其他地方。每个节点都会有它的数组索引，当我在堆中移动指向节点的指针时，我会用它的新数组索引更新节点。因此，删除节点的请求可以为我提供该节点。我将节点的存储索引用于堆中，并删除该指针，所以现在是 log(N)。只是看起来要复杂得多。
鉴于单独分配非移动节点并保持其数组索引字段更新的额外开销，听起来可能比一些非常偶然的线性搜索要多。 OTOH，将节点与数组堆分开的一个优点是交换指针比整个节点更快（在我的例子中可能是 32 个字节或更多）。
有更简单的想法吗？
好的。 你可以留在记忆中：
- 您的数据结构，包含有效负载和优先级，动态分配。结构（指针）的地址是
removal key. - 保留和维护二进制堆，包含
pointers这些数据结构。但是，heapify 元素根据优先级，包含在结构中，通过指针。
因此，您的算法：
插入：创建数据结构，将指针部署到堆，重新平衡堆：Log(N)
删除最后一个：从堆中取出最后一个元素，删除结构，从堆中删除最后一个元素，重新平衡堆：Log(N)。
删除随机元素：获取元素的指针，通过指针获得优先级，在堆中按优先级搜索此元素：Log(n)。删除结构，从堆中删除指针。重新平衡堆 - 再次 Log(N)。
数据节点在入队时分配，出队时释放，不移动。当你排队数据时，你的 return 值是这个节点的地址，尽管为了保持 API 干净，return 值的类型是不透明的。
堆是指向这些节点的指针的堆。
数据节点有一个无符号整数，它保存指向它们的指针的当前数组偏移量。
当我们移动指针（由于插入或删除等堆操作）时，我们更新它的节点索引。例如，如果我们确定我们的键比我们的父级优先级更高，我们将我们的父级移动到我们当前的位置，如下所示：
apnode[i] = apnode[iParent];
apnode[i]->iOffset = i;
插入任何键的数据，以及删除具有最高优先级键的节点，工作正常。两者都是 O( log n ).
删除尚未成为最高优先级的节点的新操作涉及将不透明键强制转换回指针，取消引用以获取相应指针的当前偏移量，然后将其删除。因此，到达要删除的指针的时间非常快 O(1)。此时，正常删除它是通常的 O( log n ).
支持此随机删除的额外开销相当于设置该偏移量。它只是一行代码，但另一方面，与没有此功能的指针堆相比，它大大增加了所触及的缓存行集。另一方面，作为指针堆的堆可能比实际将数组元素作为节点本身要快得多。
几乎完全跑题了，但对任何阅读本文的人都非常有用：
似乎所有的教科书都是这样介绍堆操作的：将您的项目添加到堆的末尾，然后进行交换以将其堆化到它所属的位置。不过，这些交换中的每一个都是三个指令。将指向堆末尾的指针视为新数据的候选目的地 (CD) 更有效，但还没有将其写入那里。
然后，将新数据的密钥与父数据进行比较。如果新数据的优先级较低或相同，则将其写入 CD 并完成。否则，只需复制 parent 到 CD，parent 的地址就成为新的 CD。重复。这将实际数据移动减少了 2/3。