求最快办法在 heap删除最后一个加入元素然后在加入一个新元素 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 求最快办法在 heap删除最后一个加入元素然后在加入一个新元素

相关主题
● 请教几个面试问题	● 问一道数组题
● Bloomberg面经	● T家电面一般有几轮？ [UPDATE面经]
● a very difficult interview question	● 吐槽一个面试
● n个点，找出离原点最近的100个点	● 备考google onsite, 讨论堆排序的时间复杂度
● 问两道google面试题	● 今天面试问题：有一个整数数组，如何find kth smallest element,如果数据是dynamic
● 问个google面试题	● 给一个最大堆，求最大的K个数，O(K) 算法？
● 问个题	● Top K in N sorted array
● Ask a google interview question	● A家电面面经

相关话题的讨论汇总
话题: heap话题: 加入话题: 元素

进入JobHunting版参与讨论

1

(共1页)

C**5 发帖数: 202	1 如何log(n) ?
q****m 发帖数: 177	2 感觉需要记录最后加入的元素的指针【在 C**5 的大作中提到】 : 如何log(n) ?
l*n 发帖数: 529	3 必须要有map记住每个加入数据的位置，并且每次swap都要更新。删除的话，可以参看http://stackoverflow.com/questions/8705099/how-to-delete-in-a-heap-data-structure 【在 C**5 的大作中提到】 : 如何log(n) ?
c**y 发帖数: 172	4 不是很明白你的问题。heap是如何实现的？用array吗？如果是的话，replace array的最后一个元素，然后从新heapify，O(log n)就可以了？ Worst Case(从新build一个heap)也是O(n)的。

1

(共1页)

进入JobHunting版参与讨论

相关主题
● A家电面面经	● 问两道google面试题
● (CS) heapify a binary tree	● 问个google面试题
● 请教个面试题：大数据求中值	● 问个题
● 不明白“整数流的中位数”为啥用max heap和min heap比binary sort 好	● Ask a google interview question
● 请教几个面试问题	● 问一道数组题
● Bloomberg面经	● T家电面一般有几轮？ [UPDATE面经]
● a very difficult interview question	● 吐槽一个面试
● n个点，找出离原点最近的100个点	● 备考google onsite, 讨论堆排序的时间复杂度

相关话题的讨论汇总
话题: heap话题: 加入话题: 元素

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)