a********1
发帖数: 750 | 1 heap只是优先队列的数据结构，怎么实现可以自己去实现，比如fibonacci heap 通常
就不用数组 |
|
|
H*X
发帖数: 281 | 3
你说的heap,和lz帖子里的heap,不是一个东西吧, lz是在讨论memory allocation |
|
w*********l
发帖数: 1337 | 4 说得基本没错。但是heap在程序死亡的时候也会被释放。所有进程占用的资源都会被释
放。memory leak不是因为heap不释放，是因为usage会一直增长不降。static空间根本
不会增长，所以也不用担心释放的问题。 |
|
H*X
发帖数: 281 | 5 所以我意思说, 一个是在data seg里,一个是在heap上,就可以算为2种空间了,否则我也
不太明白,heap还能怎么分 |
|
t**g
发帖数: 1164 | 6 我知道new出来的是放在heap
local variable是在stack
不知道下面的呢？
global variable?
gloval static variable?
local static variable?
我听到一个说法是heap里创建的变量都要自己手动delete
请问是对的么？ |
|
s*********t
发帖数: 1663 | 7 heap sort很常用，比如找top k，动态的，就可以开个k size的heap
merge sort我在搜索引擎的应用里用过，搜两个关键字，索引返回两个集合，这时候需
要合并。 这两个集合应该是有序的，此时只需要merge sort的merge即可。
qsort很省事，一般的排序，算法题目，都可以使用。 |
|
l*******y
发帖数: 1498 | 8 quick sort时间依赖于pviot，最好情况下才是nlgn，但是有较好的cache behavior.
heap sort 最差情况下是nlgn，但是heap sort 有很多random access，如果数据是从
high latency的设备上读的话会比较慢。
merge sort最差是nlgn，需要额外的空间(上面2个sort都可以in place完成)，也有比较好的cache behavior，还有merge sort更容易parallelize |
|
v*******7
发帖数: 187 | 9
对，如果heap用binary tree来表示，那么需要有parent指针的信息，in place可以做
，我这里刚
才想了一个算法，是O(nlgn)的做法，可以做到。
我在想用array表示的heap转换成array 表示的BST要怎么做。 |
|
C***y
发帖数: 2546 | 10 why not quick sort on the heap?
这样的话还是O(nlogn),但是不需要额外空间
———————————————————
俺错了，heap sort是O（1）的空间 |
|
y**i
发帖数: 1112 | 11 是只有用new操作符分配的对象实例才在heap里。
如果在函数里写：
string s, *ps = &s;
这个还是在stack里。
必须string *ps = new string;
才在heap里 |
|
s****n
发帖数: 48 | 12 heap有什么property?不就是root节点特别一点吗？把最后一个元素移到被删除节点，
heap size减一不就行了吗？
Am I missing something? |
|
n****r
发帖数: 120 | 13 假设heap是max Heap。
可以直接对要删除的节点i和最后的节点N交换，然后
1.若要删除的节点比最后节点小，执行siftUp，否则siftDown
2.删除最后的节点
这样应该就可以，不需要先和根节点交换 |
|
|
d****n
发帖数: 1637 | 15 //in windows
#include
#include
using namespace std;
class A{
public :
int a;
int b;
};
int main()
{
cout<<&main<
int before=4;
cout<<"STACK &before="<<&before<
A objA;
void *p=malloc(1000);
cout<<"HEAP *p="<
cout<<"&objA.a"<<&(objA.a)<
cout<<"&objA.b"<<&(objA.b)<
cout<<"objA="<<&objA<
int after=4;
cout<<"STACK &after="<<&after<
return 0;
}
//output from windows wi... 阅读全帖 |
|
d****n
发帖数: 1637 | 16 thanks for you advice.
I just add a function in main()
print a local variable from fun()
Something like this.
void fun(){int a; cout<<&a<
main(){
fun();
}
###win32
0035119A
STACK &before=002BF998
HEAP *p=005D83E0
&objA.a002BF988
&objA.b002BF98C
objA=002BF988
STACK &after=002BF970
&a=002BF890 //local variable from fun()
###x64
000000013FB41000
STACK &before=00000000001BF798
HEAP *p=00000000005B67A0
&objA.a00000000001BF7A8
&objA.b00000000001BF7AC
objA=00000000001BF7A8
STACK &after=000000... 阅读全帖 |
|
j*****y
发帖数: 1071 | 17 sorry, 我这里讲的 Heap 就是 二叉堆 binary heap |
|
j******2
发帖数: 362 | 18 heap常考就俩题
1. in stream找中值
2. in stream找top k（特别是频率最高的top k)
programming |
|
a********m
发帖数: 15480 | 19 不对。用heap实现的话还是lgn，这样应该就可以了。
这样回答lz的问题就是heap需要随机访问元素。其它简单类型比如queue,stack都不符
合这个要求。 |
|
c**y
发帖数: 172 | 20 不是很明白你的问题。heap是如何实现的？用array吗？如果是的话，replace array的
最后一个元素，然后从新heapify，O(log n)就可以了？
Worst Case(从新build一个heap)也是O(n)的。 |
|
d********i
发帖数: 582 | 21 小弟请大哥们指教，谢谢。
以下两种build heap的方法。
第一种用PriorityQueue建的heap,请问是O(n)还是O(nlogn)?
第二种不用PriorityQueue,请问是是O(n)还是O(nlogn)。
第一种：
PriorityQueue minHeap = new PriorityQueue();
for (int i : a) {
minHeap.add(i);
}
第二种：
public static void buildMaxHeap(int[] a) {
int i = (a.length - 1) >> 1;
while (i >= 0) {
maintainMaxHeap(a, a.length, i);
i--;
}
}
public static void maintainMaxHeap(int[] a, int heapSize, int i) {
int l = (i << 1) + 1;
int r = (i << 1) ... 阅读全帖 |
|
n*****g
发帖数: 178 | 22 在网上看到这题在：Sort numbers stored on different machines
出处：http://www.geeksforgeeks.org/sort-numbers-stored-on-different-machines/
Given N machines. Each machine contains some numbers in sorted form. But the
amount of numbers, each machine has is not fixed. Output the numbers from
all the machine in sorted non-decreasing form.
Example:
Machine M1 contains 3 numbers: {30, 40, 50}
Machine M2 contains 2 numbers: {35, 45}
Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
... 阅读全帖 |
|
s***i
发帖数: 503 | 23 C++用priority_queue，Java用PriorityQueue，你不需要自己
实现min heap的，除非面试的人专门要考你怎么实现min heap，
那时候你再另外写一段code实现。 |
|
c*********h
发帖数: 102 | 24 原题在这里：
http://www.geeksforgeeks.org/median-of-stream-of-integers-runni
Given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -... 阅读全帖 |
|
c*********h
发帖数: 102 | 25 什么意思？如果考虑space，heap不是也一样？ |
|
b******i
发帖数: 914 | 26 问问，因为multiset实在写习惯了，新的priority_queue反而怕出bug。
请问面试的时候用multiset来代替heap可以吗（如果不要求实现heap本身的话），
multiset是基于红黑树的，复杂度应该都是log(n)的。 |
|
P******r
发帖数: 1342 | 27 你pivot怎么选？每次去掉一半是最优状况。最差状况每次只能去掉一个吧。
：很多家都有这题，假如有很多points，找出离原点最近的k个点。
：做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有 |
|
o******0
发帖数: 105 | 28 但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
queue吧？ |
|
l**o
发帖数: 356 | 29 Priority_queue有size（）啊，每次比较一下size，多出来的pop掉最小的不就可以了？
但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
queue吧？ |
|
发帖数: 1 | 30 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
top k 的问题都用heap 呢？
按理说应该用最快的quick selection啊。 |
|
z*i
发帖数: 58873 | 31 是英国作家Angie Sage的一套Fantasy小说集，全书一共7本（Magyk，
Flyte， Physik， Queste，Syren，Darke，Fyre），于2005～2013先后出版。这套书
的目标读者群是孩子，所以非常简单易读。
这套系列的世界设定比较简单。开始的主要的地点是Castle, Port, Marsh, Forest。
特别技能/专业有Wizard，Queen，Witch。虽然在第三本以后慢慢的时空都有所扩展，
但是跟别的fantasy系列里面庞大复杂的时空和技能树相比，SH的魔法世界简单的多了。
故事的同名主人公Septimus Heap出生在一个传统的Wizard家庭，由于是第七个儿子的
第七个儿子，所以被认为具有超凡的魔法潜力。整套书围绕的就是他从出生以后如何一
步步的成长成为ExtraOrdinary Wizard的。值得一提的是虽然Septimus是同名主人公，
但是公主Jenna在书里的戏份完全不比Septimus少，而且从Princess到Queen的整个过程
中性格的成长和行为的变化其实比Septimus更加丰富和... 阅读全帖 |
|
n****n
发帖数: 101 | 32 如果说一个heap只要求任一节点i不大于其两个子节点2i、节点2i+1，那么，一个已经
排好序的数组，就是一个heap？ |
|
q*******i
发帖数: 353 | 33 【 以下文字转载自 Java 讨论区 】
发信人: qqwuweiyi (娓娓), 信区: Java
标 题: java heap space out 问题
发信站: BBS 未名空间站 (Fri May 14 23:50:54 2010, 美东)
每次运行都提示Java:out of memory : heap space
这个问题怎么解决？谢谢 |
|
o****i
发帖数: 1706 | 34 【 以下文字转载自 Linux 讨论区 】
发信人: ouyadi (可乐会捂帮帮众), 信区: Linux
标 题: Valgrind报uninitialized value was created by a heap allocation
发信站: BBS 未名空间站 (Sat Feb 19 12:11:20 2011, 美东)
程序运行正常，可是在测memery leak的时候报上面那个错，具体错误消息如下：
==25663== Conditional jump or move depends on uninitialised value(s)
==25663== at 0x400C9F: add_edge (graph.c:59)
==25663== by 0x40071A: main (main.c:13)
==25663== Uninitialised value was created by a heap allocation
==25663== at 0x4A0515D: malloc (vg_replace_malloc.c:195)
==256... 阅读全帖 |
|
i****k
发帖数: 804 | 35 首先要根据exception确定是哪一种 OOME。
常见的 OOME 根据HEAP区域有两类：PermGen 和 Heap。PermGen 类的OOME只会出现在
有permgen概念的JVM，比如HOTSPOT。BEA 的 JROCKIT 不会出现这种问题。
PermGen存放两种对象：Class object 和 interned String。大多数permGen OOME由前
者引起，根本原因是hotspot对 classloader 的 garbage collection 做的不是很好。
这种问题常出现于：1. 开发过程中反复deploy程序。2. 应用的high availability
strategy或者side-by-side deployment strategy 采用了抛弃classloader的设计。3.
病态JSP,TAG, EJB compiler。
PermGen OOME 是常见，well documented，但是普通人极难处理的问题。这类问题的根
源多数在于JVM, SERVER 和应用架构的弊病。其中应用架构问题，常见病因有：
1.误用Thre |
|
i****k
发帖数: 804 | 36 另外，1.5G对于大多数SERVER是足够了。这个具体要参考你的SERVER的厂商文档。
增加HEAP到2G以上，或者上64位JVM，至少在目前，几乎可以肯定不是正确答案。前者
在某些JVM/OS KERNEL 组合下不能用。后者即使能用，一般而言性能也比32位差。
JAVA 的 SCALABILITY STRATEGY 主要是横向。比如，一台机器上部署多个JVM构成
CLUSTER要比增加HEAP或者64位内存有效。 |
|
s*******e
发帖数: 174 | 37 String s1 = "grapefruit";
String s2 = "grapefruit";
请问 s1 and s2 是在 stack 还是 heap 上呢？ Does s1 and s2 point to same
address?
String s3 = "grape"+"fruit";
Does s3 point to same address as s1 and s2?
String s4 = new String("grapefruit");
String s5 = new String("grapefruit");
s4 and s5 should be in heap, s4 and s5 should point to different addresses,
right?
System.out.println(s1+s2);
System.out.println(s4+s5);
which one is faster? Thanks |
|
s*******e
发帖数: 174 | 38 faint, 这道题果然引起争论，在网上也找不到标准答案。。
我自己觉得 s1, s2 points to same address in the heap,
s4 and s5 points to different addresses in the heap.
s4 + s5 is slower than s1+s2..
但是C++背景的人会说 s1, s2 are in stack. Java is different, it stores local
variables and active method invocations in stack. |
|
c*********n
发帖数: 1057 | 39 In my opinion, s1, s2, and s3 are in heap and point to the same address.
s4 and s5 point to different addresses in heap |
|
g*****g
发帖数: 34805 | 40 They don't have the same address, but have some sort of the
same internal address.
s1 = "abc";
s2 = new String("abc");
while s1!=s2, s1.intern()==s2.intern()
I think there's only one string created in heap, while references may
be on heap or stack depends on where you declare it. |
|
g***l
发帖数: 2753 | 41 帮人查一个js程序的memory leak问题，在触发garbage collector之前，有没有
办法知道这个js程序中的所有objects在heap中的状态。
比如我能不能加入一段代码去拿到当前用了多少M的heap?
谢谢 |
|
c*********e
发帖数: 16335 | 42 declare的时候要new的就是在heap. int,boolean不在heap. |
|
g*****g
发帖数: 34805 | 43 The array (an object) is stored on the heap, the reference can be stored on
heap or stack, depending on whether it's an instance variable. |
|
p*****2
发帖数: 21240 | 44
好像不是。zhaoce是回答上边的问题的。感觉意思是说如果ref和val都放在heap里就慢
了。因为上边的问题是问为什么val在heap，ref在stack。 |
|
x****d
发帖数: 1766 | 45 i didn't read the whole thread. But guys, can you pickup a preparation book
for oracle/sun certified java developer exam? It is summarized very clear in
that book, what is in the heap and what is in the stack.
that is why I advocate scjp exam for all java developers.
Another recommendation, read ibm article, from java code to java heap,
google it. |
|
s******e
发帖数: 493 | 46 I doubt that a simple yes or no will be able to answer this question
correctly.
Java objects basically can be divided into class object and instance object.
All instance objects are saved in the heap. Even for a static member of a
class. In such a case, only the class variable will be in permgen. But all
class objects will be in permgen.
If my memory is correct, JMM spec mentions four types of memory space: stack
, heap, permgen and code cache. |
|
z*******3
发帖数: 13709 | 47 这个我狗了一下哈
发现permgen只有hotspot有实现
其它的jvm都没有实现，而且在逐步淘汰permgen
那方法区理论上已经算是heap的一部分来实现了
那笼统地可以认为都在heap里面
规范里叫做方法区的抽象区域，与“永久代”并不等价。只是在现在的Oracle (Sun)
HotSpot使用“永久代”来实现方法区而已。
服务器端主流的高性能JVM现在就三种，一个是HotSpot（其中Sun的原始版本用得最多
，由其衍生出来的Azul版与HP版也颇有应用；Apple的Mac OS上的JVM也是从Sun的版本
衍生出来的，不过拿Mac来做服务器的大概不多吧）；一个是Oracle (BEA)的JRockit；
还有一个是IBM的JVM，现在主要在用的是J9。这之中，只有HotSpot是有PermGen的，而
JRockit与J9都没有；连Azul版HotSpot也经过改进早已去除了PermGen。概念上说这些
JVM都有符合规范的“方法区”，但并不一定要用PermGen来实现就是了。
甚至连Oracle (Sun)的HotSpot也实质性开始去除PermGen的工作了。请参考最近... 阅读全帖 |
|
l**********r
发帖数: 4612 | 48 【 以下文字转载自 Programming 讨论区 】
发信人: linuxbeginer (linux), 信区: Programming
标 题: Char x[] = "abc"; 是在heap还是stack上？
发信站: BBS 未名空间站 (Mon Oct 19 17:15:12 2009, 美东)
Char x[] = "abc";
我认为内存allocated 在heap上。对么？ |
|
W*********g
发帖数: 409 | 49 You are talking about the default heap. You can create your own heap with
certain option to avoid that. |
|
l*******p
发帖数: 7 | 50 语言：c++
网上查了一下，有的说是heap,有的说机不再heap也不再stack
请问到底再哪里？
先谢了 |
|
