The tag has no wiki summary.

learn more… | top users | synonyms

9
votes
3answers
2k views

Java Heap Allocation Faster than C++

I already posted this question on SO and it did ok. It was unfortunately closed though(only needs one vote to reopen) but someone suggested I post it on here as it is a better fit so the following is ...
4
votes
2answers
2k views

How are the size of the stack and heap limited by the OS?

Note: if you need to consider a specific OS to be able to answer, please consider Linux. Whenever I run a program, it will be given a virtual memory space to run in, with an area for its stack and ...
3
votes
1answer
113 views

Is there a name for a randomized heap?

I've made a container which functions like a Binary Heap in terms of insertions and popping the root element. The key difference is that the comparison steps are all replaced with a random call for ...
1
vote
6answers
2k views

Heap overflow vs stack overflow

So as a general rule to avoid a stack overflow, big objects should be allocated to the heap (correct me if I am wrong). But, since the heap and the stack expand towards each other, wouldn't this cause ...
2
votes
4answers
685 views

Applications of heapsort

Heapsort is a sorting algorithm that has a time complexity of O(nlogn), and performs sorting using O(1) space complexity. However, I know that because it's unstable, it doesn't find many applications ...
6
votes
3answers
4k views

A good C Variable Length Array example

This question got rather a freezing reception at SO, so I decided to delete it there and try here instead. If you think it does not fit here either, please at least leave a comment on suggestion how ...
1
vote
1answer
192 views

Marked nodes in Fibonacci heaps

I don't understand why Fibonacci heaps have marked nodes (picture). A node is marked when its child is deleted. Quoting from Wikipedia: "[Keeping degree of each node low] is achieved by the rule that ...
8
votes
1answer
317 views

Why is the main memory for object allocation called the 'heap'?

Has anybody got an idea why the area of main memory where objects are allocated is referred to as the heap. I can understand the rationale for that of the stack LIFO but would like to know what the ...
4
votes
1answer
305 views

How does a priority_queue maintain a heap on a deque efficiently?

In the C++ STL, priority_queue (heap) can be used with any underlying container, such as a deque. How does the implementation stay O(log n) if deques don't swap an item in index a with index b in ...
0
votes
0answers
315 views

find second smallest element in Fibonacci Heap

I need to describe an algorithm that finds the second smallest element in a Fibonacci-Heap using the Operations: Insert, ExtractMin, DecreaseKey and GetMin. The last one is an algorithm previously ...
4
votes
4answers
1k views

Stack and heap - dynamic allocation question

Sources usually mention that dynamically created variables are allocated on the heap, while functions' variables on the stack. Also the ones on the stack cease to exist automatically when e.g. the ...
1
vote
5answers
499 views

Java heap space

In Java/JVM, why do we call the memory place where Java creates objects as "Heap"? Does it use the Heap Data Structure to create/remove/maintain the objects? As I read in the documentation of Heap ...
-3
votes
1answer
502 views

Construct an array from an existing array

Given an array of integers A[1...n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ..., A[i+K-1]), where K will be given. Array B will have ...
1
vote
1answer
193 views

Common diagnostics which VisualVM is used for

There's a lot of documentation out there on how to use the 'jvisualvm' profiler, but very little (if any) real-life advice on how to analyze all those charts and dumps. I'm just a little overwhelmed ...
5
votes
2answers
2k views

Custom heap allocators

Most programs can be quite casual about heap allocation, even to the extent that functional programming languages prefer to allocate new objects than modify old ones, and let the garbage collector ...
2
votes
1answer
2k views

At a higher level description, how is DLMALLOC supposed work?

There doesn't seem to be that many good descriptions that go into the specifics about how dlmalloc works. The sources I have come across so far mention dlmalloc, but then only goes on to explain what ...
3
votes
1answer
193 views

Are there some good algorithms for implementing a Heap that minimizes fragmentation?

Right now I'm trying to create a Heap that requires 8-byte alignment, and was looking around online for some good methods that would minimize the amount of fragmentation. Less fragmentation is ideal, ...
3
votes
1answer
170 views

Heaps: Why is there a tradeoff between amount of space occupied (fragmentation), and speed at which operations are carried out?

Apparently, the two major judging criteria of the effectiveness of heaps are (1) how much we can minimize the amount of space it takes up and (2) how fast operations on the heap can be carried out, ...
5
votes
2answers
333 views

Why in the world does a heap need to make sure it allocates in 8-byte alignments?

4-bytes = word; 8-bytes = 2x word Then why doesn't the heap just go with 4-byte alignment (because it will be grabbing a word at a time anyway, right?) If we went with 8-byte alignments, why not 12? ...
13
votes
6answers
3k views

Why do we need a Heap if everything can be done much more efficiently on the Stack?

This is actually somewhat related to the question I asked yesterday about why both a Stack and a Heap are necessary in the applications we use today (and why we can't just go with a Heap instead of ...