Y********f
发帖数: 410 | 1 测试过的代码：
#include
#include
using namespace std;
void deleteNode(int heap[], int n, int pos)
{
// put the last elements to where the node removed
heap[pos] = heap[n-1];
// adjust elements above pos
int i = pos;
while(i != 0 && heap[i] < heap[(i - 1) / 2])
{
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
// adjust elements below pos
i = pos;
while(true)
{
if (2 * i + 1 > n -2)
{
//al... 阅读全帖 |
|
b**i
发帖数: 2 | 2 楼上说的对，用make_heap, pop_heap, push_heap 来做。
vector heap;
heap.push_back(1);
heap.push_back(2);
make_heap(heap.begin(), heap.end()); // 这样就把heap变成了一个max heap
auto cmp = [](int lhs, int rhs){return lhs > rhs;};
make_heap(heap.begin(), heap.end()); // 把heap变成了 min heap
下面都用minheap举例子，如果是maxheap不需要传第三个参数。
pop_heap(heap.begin(), heap.end(), cmp); // 现在 heap.back() 是heap的最上面
的那个元素，已经pop出来了
heap.push_back(998);
push_heap(heap.begin(), heap.end(), cmp); // 这样就把998正确插入到minheap了
heap的top应该可以通过front() 来... 阅读全帖 |
|
s****s
发帖数: 628 | 3 这个例子好,我就抛砖引玉,大家一起来讨论:
void foo(){
int *p; // 1. p 在stack还是heap?
M *m; // 2. m 在stack还是heap?
p = new int[20]; //3. p 在stack还是heap?
m = new M(); //4. p 在stack还是heap?
int *p1 = new int[20];//5. p1 在stack还是heap?
M *m1 = new M(); //6 .m1 在stack还是heap?
int *p2 = NULL;//7. p2 在stack还是heap?
M *m2 = NULL;//8, m2 在stack还是heap?
}
大家直接给出1, 2,3 ,4, 5, 6, 7,8 的答案吧. 免得我更糊涂.
地方 |
|
b****g
发帖数: 192 | 4 1. in stream找中值：就是维护两个size最多相差1的heap，一个min heap，一个max
heap
2. max value top k：size为k的min heap
请问这么做对吗？
频率最高的top k 怎么做？heap里存的东西是出现的次数吗？需要一个hashtable来把
value和heap里的node进行map吗？ |
|
l*****g
发帖数: 685 | 5 heap适用于search最大或最下k个值；BST是适用于search任意一个值
如果数组有序，构成BST的time complexity是O(n); 如果无序，是O(nlogn);
如果数组有序，那该数组本身就是个heap (ascending --> min-heap; descending -->
max-heap), 无须再改变，no time complexity; 如果数组无序，构成heap是 O(
n);
好像没有O(logn)实现heap 和 BST 的方法 |
|
Y********f
发帖数: 410 | 6 面试中问到的heap是指数组结构(A[i]的children是A[2*i], A[2*i+1])呢，还是树结构
？如果是树结构，是不是BFS中前面的节点都是两个children？
最近看了两道题有关heap的题都有点无从下手：
1.Convert a min heap to BST without changing its structure and of course no
extra space(感觉这道题中heap是树结构）。
2.Convert a max heap to min heap.
谁来给点思路？ |
|
w***g
发帖数: 5958 | 7 是刚好名字相同。数据结构中的heap本质上是一种树结构。内存中的heap本质上是一种
线性结构。内存中的heap是和stack相对的，heap往上长，stack往下长，heap用来存全
局动态数据，stack用来存局部动态数据。不过内存中的stack倒是按照数据结构的
stack存放的。 |
|
t**g
发帖数: 1164 | 8 一道面试题
What is the difference between stack, static heap and dynamic heap?
我明白stack/heap的区别
可是啥叫static heap/dynamic heap?? |
|
s********a
发帖数: 1447 | 9 你是说
static heap和dynamic heap是分配了heap后 自己用数据结构实现的？
static heap用数组实现 dyanmic heap用树实现？ |
|
g*********s
发帖数: 1782 | 10 then how to ensure the heap operations' complexity is still O(logN)? for
linked list you can't randomly access the element.
why not assuming the heap is also a binary tree? the array format of heap
is just a compact representation of heap.
even if the input heap is represented as an array, we can still store the
newly bst to the array. but it would need O(1) space for array element
swap. i think this is OK. |
|
z*******3
发帖数: 13709 | 11 在stack里面的是地址或者原始数据类型
如果把所有数据都放在stack里面放不下
只能放下一些简单的数字
所以对于类这种尾巴大的东西
在stack里面保存一个地址
然后真正要用的时候就从stack里面取出地址
然后在heap中找到后再用
所以所有的对象都在heap里面
除非你不把它定义成类的对象
Integer i = new Integer(2);
这个就有在heap里面创建对象
int i = 2;这个就没有在heap里面创建对象
另外这个引申了之后是==和equals的差别
＝＝比较的是stack里面的数据是否相同
equals要override，一般来说是判断heap里面每一块的数据是否相同
再高级一点是String特殊对象的对象池
然后就是1.5的autoboxing，int i = new Integer(2);
这种方式的使用，不明确区分原始数据类型及其包装类 |
|
C**********n
发帖数: 100 | 12 问个很基本的问题。
假定某个binary search tree和max heap都是有输入一些数字序列所构成，
那么是不是binary search tree跟输入数字的顺序无关，只可能有一种binary search
tree,
但max heap(或min heap)则跟输入数字的顺序有关，同样的几个数字，输入顺序不同所
形成的max heap也不一样？ |
|
n***r
发帖数: 105 | 13 一般来说没有static heap这种说法。不是说data segment吧？
能google出来的就这些了。似乎某些程序会预先跟OS reserve some static memory
heap。
To ensure predictable performance, Flash Lite reserves a fixed-sized chunk
of memory from the operating system (OS) to create what is called a static
memory heap. This memory is reserved when the player starts up and the size
is defined by the device manufacturer.
The OS (based on design by the manufacturer) can optionally provide the
player with additional memory called dynamic memory heap. Flas |
|
s**9
发帖数: 207 | 14 请教两个问题：
1。这种data segment， code segment的组织是CPU决定的还是操作系统决定的？所有
机器都这样吗？
2。heap这个名字和数据结构中的heap有什么关系？好像memory的heap并不是用数据结
构的heap来组织的？
谢谢 |
|
j*****u
发帖数: 1133 | 15 Not sure about Java... does Java has boxing/unboxing also?
if so, primitive (value) type could be in the heap as well:
object o = 1234;
besides boxing, there're other cases that value type does not live in the st
ack, an exmaple is array of value type.
int[] myArray; // all int value of the array lives in the heap.
So, it is not accurate to say "value type goes to the stack, reference type
goes to the heap".
also, there is no variable "name" in the stack, it is actually an address (x
86: 4 bytes... 阅读全帖 |
|
g**********y
发帖数: 14569 | 16 heap to BST, 我只知道个不完美的答案，把heap sort后，依次填回heap结构中，用
successor()。
BST to heap, 有人给出答案：
public void bst2heap(int a[]) {
int n = a.length;
reverseArm(a, 0, n);
for (int i = 1; i < n / 2; i += 2)
reverseArm(a, i, n);
}
private void reverseArm(int a[], int from, int n) {
int to = from;
while (to * 2 + 2 < n)
to = to * 2 + 2;
while (to > from) {
int t = a[to];
a[to] = a[from];
a[from] = t... 阅读全帖 |
|
g*****e
发帖数: 282 | 17 k sorted array merge有很多解法，根据各array长短的情况各种算法效率各异。大家
一般还是选择建个k heap而不是每次选两个array merge吧？那样的话写个heap实现还
是挺麻烦的。能假设有现成的min heap或者max heap可以调用么？哪位朋友实际面试里
碰到过的讲讲吧。多谢！ |
|
b****g
发帖数: 192 | 18 Leetcode的题型很全面，包括hashtable、map、tree、dfs/bfs、dynamic programming
、stack、queue都有，但是貌似heap的不多。
谁有C++的heap的例题？最好有答案，我就能自己看看了。
只看到有make_heap、posh_heap、pop_heap的函数。有没有完整的像stack那样封装好
的heap类？ |
|
f****p
发帖数: 18483 | 19 在一般情况下，quick sort比heap sort快是因为下面几个原因。
1）quick sort没有事先的准备。heap sort一开始要建堆。
2) quick sort 在一个pass以后，分界的那个element就是最终结果，一个pass的cost
和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整，就
是差不多logn，乘积也差不多是nlogn。
3) 如果是多个cpu，多个thread，quick sort 绝对要比heap sort 强。
其实quick sort 主要的强的就是1) |
|
f****p
发帖数: 18483 | 20
我其实还好少说了一个。
quick sort把一个分裂成两个的时候，理想情况是平均分。而下一步两个子表的长度都
是那个父表的一伴。而heap sort则不是。
你仔细观察这个动画。heap的准备和每一步做的都有。
http://en.wikipedia.org/wiki/Heapsort
如果一般情况下
quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
= n * log(n)
heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
所以尽管heap sort 是 n log(n)，quick sort基本上是最优的。
为了达到最优效果，对于大的n，一般还会做个randomization。很多randomized
algorithms就是这个思路。一般就一两遍就可以达到了，就是说再加上个n 或者 2n。 |
|
|
c*********e
发帖数: 16335 | 22 是不是这些：
-XX:InitiatingHeapOccupancyPercent=n Percentage of the (entire) heap
occupancy to start a concurrent GC cycle. It is used by GCs that trigger a
concurrent GC cycle based on the occupancy of the entire heap, not just one
of the generations (e.g., G1). A value of 0 denotes 'do constant GC cycles'.
The default value is 45.
-XX:MaxHeapFreeRatio=70 Maximum percentage of heap free after GC to
avoid shrinking.
-XX:MinHeapFreeRatio=40 Minimum percentage of heap free after GC to
avoid ... 阅读全帖 |
|
e***r
发帖数: 68 | 23 hmm.......有人说内存中的heap和数据结构的heap是没有关系的...内存中的heap更像
Linked List. |
|
C**********n
发帖数: 100 | 24 呵呵，
那给定一些数字，我想构造一个Max heap或Min heap，
那按level order traveral能否构找出我想要的那个Max heap? |
|
s*******e
发帖数: 174 | 25 【 以下文字转载自 Java 讨论区 】
发信人: shrubRose (喵喵喵), 信区: Java
标 题: 一道 JAVA Stack vs Heap 题
发信站: BBS 未名空间站 (Mon Nov 9 13:59:15 2009, 美东)
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.print |
|
t**g
发帖数: 1164 | 26 这里的heap其实已经超越了C++本身范畴把？
int *a=new int[100] //这里是static heap?
能举一个用dynamic heap的C++代码语句么？ |
|
w*********l
发帖数: 1337 | 27 那样的话heap根本不可能是dynamic的。都是固定地址空间。是heap就要被malloc (或
者衍生的C++的new等等）。
你说的这个static variables其实跟global一样，是在bss(block started by symbol)
，跟heap一点儿关系都没有。 |
|
h*****g
发帖数: 944 | 28 同样一组数，在做什么问题是做成heap比较好search, 做什么问题时做成BST比较好
search?
把一组数做成heap和BST,的time complexity都是O(n)吗？
能不能用o(logN)来实现一个heap或者BST?
谢了
BST = binary search tree |
|
H******7
发帖数: 1728 | 29 heap是tree实现的。
那heap有什么特别呢，很少用这个，我自己。请教高手，heap有设呢么特殊之处 什么
时候用合适？多谢多西 |
|
u******e
发帖数: 758 | 30 heap是的基础是tree，但并没有是tree实现这一说
tree本身可以是linked list,可以是array
heap绝大多数情况下应该说是用array实现的，一个比较经典的问题，就是你可以用
heap来得到mitbbs上每天的十大。 |
|
x******2
发帖数: 546 | 31
是的，你说的static data area 跟我说的heap是一个东西呗...这个heap不是数据结构
里的heap |
|
P**********c
发帖数: 3417 | 32 heap是recursive定义的，每个子树也必须是heap，直接size--肯定不行的. 不过你这个也是一个思路，可以把最后一个元素移到被删除节点，然后再怎么调整一下。
但是如果被删除的点跟最后一个节点不是属于一个子树的话，貌似不太好处理。getback的那个思路应该是对的。我待会儿试下。
比如这样一个heap
10
9 2
8 7 1 0
6
你这个思路的话，如果删除的是9，那应该把6移到9的位置上然后siftdown, 如果删除的是1， 移过去之后需要siftup, 所以需要分情况讨论。 |
|
r**********g
发帖数: 22734 | 33 quick sort是O(n^2)好吧。要O(nlogn)，需要先randomize。quick sort还不是stable
的。以前说qsort快主要是cache line优化得好，如果是sort object的话其实都是一样
，我试过，用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
除对象的sorted heap对象。而现在大规模parallel，像MapReduce，其实MergeSort要
好得多。 |
|
d******l
发帖数: 98 | 34 In my opinion, quicksort() is better because the CPU cache thing, has better
locality of reference -- the next thing to be accessed is usually close in
memory to the thing you just looked at. In java, java.util.Arrays.sort()
uses quicksort(), while java.util.Collections.sort() use mergesort().
As for heapsort(), it doesn't build a real heap(tree-heap), it is array/
arraylist in fact, through the index jumping, give us an illusion of a heap.
By the way, bless for myself recent onsite. ^_^ |
|
k*******t
发帖数: 144 | 35 知道怎么用priority_queue定义min heap, 如果heap中的元素为int, 我一般用
priority_queue, cmp> minheap, 另外再另外定义下cmp。有次面试
时，面试官问我priority_queue, cmp>中，为何需要vector，
我说是个container, 其他的我就啥也不知道啦。有人知道为何c++不把这container写
死为一个类型，比如vector? 让用户自己定义container有啥优势？除了vector, 还有
其他container可以用来定义min heap么？问的问题有点弱，请轻拍 |
|
y*****e
发帖数: 712 | 36 很多家都有这题，假如有很多points，找出离原点最近的k个点。
做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有
insert/pop operation的complexity是（n-k）log(k), 综合下来是nlogk
另外一种方法是任意去pivot, 每次call partition function, 把数组按放到pivot的
左边和右边，一直到pivot = k为止，直接return pivot左边的所有点。这种做法应该
是每次去掉一半的数组
n + n/2 + n/4 +.... = 2n也就是o(n),
应该是selection sort更好啊，为啥面试官总是让写heap? 是不是有其他的考量？比如
是streaming data或者数据量太大，不能一次完全放到array里？ |
|
m****n
发帖数: 886 | 37 I'm running an application on Weblogic. I did a profile of the heap, and
find out 43% of all objects in heap are Integers and they can't be cleaned up
by GC. Why these integers stay in heap? Does that indicate a memory leak? |
|
t***a
发帖数: 416 | 38 为啥stack查找快？
为啥heap大而慢？
在stack的variable table里的要么是primitive value，要么是reference value，这
个table应该不会大，于是就查找快？我觉得stack里就是个变量数组而已，慢是慢不了
，可是也不能说就小而快了吧
如果是reference value的话，拿着这个ref value去heap里找instance，因为heap比
stack空间大，会慢。赵老师是这个意思么？ |
|
F****n
发帖数: 3271 | 39 JVM实际上只有5种类型，int, float, long, double, reference/address
不管哪中类型只要出现在 code statement (包括 method parameter)里就在Stack上
而reference 指向的类数据肯定在 heap 上
所以类的成员变量不管啥类型也在 heap 上
另外JVM的Stack 和 Heap都是抽象的，具体实现可以乱搞 |
|
z*******3
发帖数: 13709 | 40 这里面有几个小疑点
一个是方法区的实现是否在heap里面实现
还是额外滴在heap以外的地方实现
如果是在PermGen里面实现的话
就要看看static变量的主体是否在这个区里面
不过如果smectite说得是对的话
static变量其实只存引用在permgen里面
然后主体还是在heap里面
是不是这样理解？
这个是虚拟机的问题 |
|
yy
发帖数: 45 | 41 看more effective c++:
有个地方说到 heap array,
请问什么是heap array, 它何non-heap array 有什么区别？
Thanks a lot1 |
|
w*******y
发帖数: 372 | 42 We know that using heap-allocated memory is slower than stack memory. Can
anyone tell me how much slower is the heap memory allocation? A numerical
analysis on a popular implementation would be terrific, e.g., linux. Another
stupid question: after memory allocation, the access to heap memory should
be as fast as to stack memory, right?
Thanks. |
|
j****r
发帖数: 28 | 43 That depends on the location of newly allocated memory space.
If you use new to allocate a new array, it is allocated in heap. I remeber
available space in heap is huge because of virtual memory. In addition, heap
is well managed so that error is returned if your memory allocation request
can not be satisfied.
If you use static definition (like vector vec[10000]), it is allocated in
stack. In linux, some systems have default limitation about the stack size.
You can use unlimit command to chec |
|
e***r
发帖数: 68 | 44 是刚好名字相同吗？还是说内存中留做Heap的那一部分都是按照Memory Block Size的
Heap Order来存放的？ |
|
w***g
发帖数: 5958 | 45 不知道静态变量和全局变量的地方是不是叫heap，但是静态变量和全局变量大小固定，
不存在内存管理问题。也可以理解这些固定的东西在heap底部。动态分配的内存是放在
heap中的。 |
|
b***y
发帖数: 2799 | 46 ☆─────────────────────────────────────☆
nissan (Go! Milan!) 于 (Fri Mar 14 02:18:16 2008) 提到:
☆─────────────────────────────────────☆
nissan (Go! Milan!) 于 (Sun Mar 16 17:38:18 2008) 提到:
没有人回答吗？
有人说“不是。因为你可以随机访问数组。”
那么，heap难道不可以存储为数组吗，不可以随机访问吗？
如果heap不是存储为数组、随机访问，那么存储为什么呢？
☆─────────────────────────────────────☆
skatou (skatou) 于 (Mon Mar 17 13:21:16 2008) 提到:
你说的heap是priority queue么？是的话可以存成数组啊，因为priority是一个完全
二叉树(是不是这样叫的？-_-)
stl里面有对应的，make_heap，is_heap之类
☆─────────────────────── |
|
S*A
发帖数: 7142 | 47 我猜啊，公司希望可以知道比java底层的 OS 是如何玩这些的。
想问的是出现内存 swap storm 或者 memory leak 这
样的情况在 OS 这一层有什么可以做的，如何鉴别和调试。
你说的 heap 是很古老的玩法。现在 Linux 的 malloc 大一点或者多
一点的内存都是用 mmap 做的，以经不是 heap（brk syscall） 这种
单一方向增长的。64 位的虚拟地址很大，可以随便放。
如果你有多个thread， 每个tread有自己的 stack， 那个stack 就
没法一个一个和 heap 对接起来，因为有很多个。 |
|
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上。对么？
suppose char x[] is defined at global scope. |
|
s******9
发帖数: 84 | 49 基于数组的Heap是Static的，因为容量无法扩展。基于树的Heap是dynamic的。 |
|
w*********l
发帖数: 1337 | 50 这题比较confusing。这说的应该不是进程空间里的stack和heap，是stack和heap数据
结构。 |
|
