用C语言写堆

也就是优先队列,我们知道STL中提供了一个好用的优先队列priority_queue<T>,C语言中起码有不少库(比如librock)提供了这玩意,所以写这玩意纯属造无意义的轮子。但是我写这玩意主要是因为最近在面试,至少遇到了两次让手写一个堆(不过当时都没写出来,毕竟不会真的有人要手写STL提供的算法和数据结构吧?不会吧?不会吧?),闲着也是闲着,不如锻炼一下,堆还是很好写的。

我写的这个版本用void*模拟泛型,同时能自动扩容,但是缺点也很多,就我自己的感觉是时间复杂度的常数肯定很大,虽然是$O(\log_2 n)$​​​​​,但是有大量的判断,而且插入位置也没有优化,只写了个简单的测试例,总之不推荐在生产环境用(STL不香吗?)。