昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。
具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。
下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。
昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。
具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。
下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。