Questions tagged [heap]
A heap is a tree-based data structure that satisfies the heap property. For questions about memory allocated from the system heap, use the [memory-management] tag.
167
questions
4
votes
1
answer
140
views
Arbitrary Length Input in C
From scanf() to fgets(), we need to first specify the maximum length of the string input, due to which input gets a limitation, ...
- 369
4
votes
0
answers
56
views
2
votes
3
answers
194
views
Adjusting heaps efficiently
Introduction and context
I am working on a small application which involves sorting 20GB files as one of the operations. This is being done, due to memory constraints, by breaking them into ~1GB ...
- 2,435
-1
votes
1
answer
101
views
Finding the 10 most frequent words from a given file ( huge amount of words) but there are stop words [closed]
I'm using Trie and MinHeap while writing my code but I stuck at one point. While counting the most frequent words I should not count the stop words and there is a file called stopwords.txt. Somehow I ...
- 1
5
votes
2
answers
171
views
Binary Heap Structure Class C++
I wrote a binary heap structure class in C++. It is a templated class with a comparison type as one of the template parameters to allow for a min or max heap.
I have not written anything in C++ in a ...
- 195
0
votes
1
answer
53
views
Assigning Tasks to Entities (or some other entity) based on Priority
Main Questions:
Is my runtime analysis correct?
Is my approach optimal or close to it?
Is there a better way and/or improvements?
Objective:
Write an algorithm to assign ...
- 41
1
vote
1
answer
92
views
Sink algorithm in Max Heap Correctness
I am trying to determine the correctness of a helper method within my MaxHeap class.
The goal of this helper method is, given the index of any node in the Max Heap, sink it to the correct level in the ...
- 41
2
votes
2
answers
64
views
Trying for an efficient and readable heap-sort implementation
I'm looking for any sort of optimization and/or conventional practice tips, such as using the appropriate data types and naming my variables appropriately.
...
- 195
6
votes
1
answer
148
views
Binary Heap Implementation in Rust
I'm learning Rust by implementing basic data structures and algorithms. I implemented a binary heap (max heap):
...
- 163
3
votes
1
answer
170
views
Heap insertion and deletion Implementation using Python
I have implemented basic max heap insertion and deletion functions without recursion
...
- 133
2
votes
1
answer
160
views
Priority Queue implementation for top k frequent elements leetcode in Ruby
While working on the following leetcode problem: https://leetcode.com/problems/top-k-frequent-elements/ I used a Priority Queu implementation in Ruby. I have learned how to implement a Priority Queu ...
- 363
3
votes
0
answers
266
views
Another Min Heap implementation
I am having a look at Rust, this is the first data structure I have tried to implement ( the standard library has a max-heap implementation, so this is a learning exercise ).
...
- 1,246
3
votes
2
answers
90
views
Mergesort (using vectors) and some questions about memory
Back from a long C++ hiatus. I thought to implement mergesort from memory, using containers and not based on CLRS's pseudocode and arrays. The compiles and runs ok on the test cases.
...
- 285
2
votes
0
answers
176
views
Implement priority queue as min-heap in python
The standard library heapq in python doesn't support updating keys as a public method, which makes it hard to be used as a priority queue. Although the official ...
- 256
2
votes
0
answers
84
views
Max Heap Implementation in Python
I decided to challenge myself to code this data structure by just seeing how it looks visually and this is what I got. I can change this easily to minheap by changing some greater than (>) operators. ...
- 1,180
2
votes
0
answers
98
views
Fibonacci Heap Implementation In Java
From my repository.
This is my first time implementing a Fibonacci Heap, and since it's pretty complicated (at least to me), I would like to check if it is all correct.
...
- 171
4
votes
1
answer
110
views
Min Heap Java Implementation
I have implemented a min heap and looking for a simpler solution.
Is there anyone for suggesting a simpler solution for this?
Thanks.
...
- 892
-1
votes
2
answers
709
views
Finding the k most frequent words in file in c++
I have written C++ code using trie and min-heap to find the k most frequent words. I want to review my code.
...
- 11
4
votes
3
answers
1k
views
Min heap without recursion
The code reads in integer array from user input and builds a minimum heap via an iterative scheme.
Are there any edge cases in which this approach would fail?
For the following test case/command ...
- 129
1
vote
1
answer
43
views
Heap selection sort in Javascript
I have (designed and) implemented this fancy sorting algorithm that combines natural runs in the input array with a heap data structure:
...
- 26.1k
4
votes
1
answer
112
views
A heap queue in Dyalog APL
I am learning Dyalog APL. I implemented a binary heap, which seems to work. How could I make it look more like APL (and less like Python)?
...
- 195
1
vote
0
answers
43
views
Making a priority queue using a Heap. Without using queue or heapq
I have to implement a priority queue using a heap without any library / package for priority queue or heap. I made a BinHeap class which is a min heap, and I made a priority queue class with enqueque, ...
- 11
11
votes
5
answers
2k
views
Generic Heap Implementation in C#
This has been done a thousand times on here already, but here's another binary heap implementation. The implementation is generic in terms of heap elements, allows for injection of any type of ...
- 145
2
votes
1
answer
92
views
Optimizing minHeap implementation
I have implemented a java class for minHeap but it is not working as fast as I want . I want some help to change it to work faster in insertion or deleting the minimum node.
Here is my implementation:...
- 121
2
votes
1
answer
75
views
Basic LinkedList implementation [closed]
Please bear in mind, I've only started learning c++ this week, and as such, would love topic suggestions for which I should master, to become better at C++.
Below, is my code for a singly linkedlist. ...
- 33
1
vote
0
answers
217
views
Binary Heap module in Typescript/Javascript supporting min-heap and max-heap
About binary heaps: https://en.wikipedia.org/wiki/Binary_heap
The purpose of this module is to allow quick and efficient priority queue management, compared to linked list.
Efficiency: insert: \$O(\...
- 167
0
votes
1
answer
90
views
My implementation of binary heap
I made my custom heap, that allow to change and delete elements.
Please review it and tell me about any found bugs: https://bitbucket.org/nshatokhin/priorityqueue/src/master/
Is this implementation ...
- 155
4
votes
1
answer
495
views
Min Heap Tree Implementation in python 3
I wrote a min-heap using a binary tree. How can I improve the time complexity of insert and delete function to be \$\mathcal{O}(log(n))\$?
...
- 456
4
votes
1
answer
152
views
LeetCode: Merge k sorted lists C#
https://leetcode.com/problems/merge-k-sorted-lists/
Merge k sorted linked lists and return it as one sorted list. Analyze
and describe its complexity.
...
- 5,331
4
votes
1
answer
382
views
Min Heap Priority Queue
This was a part of one an assignment I found online and tried to solve it myself.
The objective was to implement a Priority Queue using Min Heap and use Array as the underlying data structure to ...
- 329
6
votes
1
answer
678
views
Implementing d-ary heap
I'm trying to Implement a d-ary heap.
A d-ary heap is just like a regular heap but instead of two childrens to each element, there are d childrens!
d is given when building a heap, either by giving an ...
- 303
4
votes
2
answers
143
views
Min Heap implementation [C++]
I've never had my C++ code reviewed before so I'd appreciate any feedback. Although my main focus was not on the implementation of the algorithm itself, any suggestions regarding improving it would be ...
- 143
4
votes
0
answers
122
views
Generic Macro Generated Interval Heap in C
When I saw this amazing data structure I couldn't stop myself from trying it! I first sought resources such as this and an article about it here. It basically works as a Max-Heap and a Min-Heap at the ...
- 347
1
vote
0
answers
240
views
Max-Heap Implementation in Kotlin
I am concerned about a few things about my heap implementation. This is in Kotlin.
For starters-
When and when not to use expressions?
The use of also to swap ...
- 61
7
votes
1
answer
816
views
LeetCode: last stone weight C#
https://leetcode.com/problems/last-stone-weight/
We have a collection of rocks, each rock has a positive integer
weight.
Each turn, we choose the two heaviest rocks and smash them together.
...
- 5,331
3
votes
1
answer
362
views
LeetCode: Minimum cost to hire k workers
https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
There are N workers. The i-th worker has a quality[i] and a minimum
wage expectation wage[i].
Now we want to hire exactly K workers to ...
- 5,331
6
votes
3
answers
5k
views
4
votes
1
answer
107
views
Overriding List subscription to create IndexedHeap for Classical Dijkstra's Algorithm
Much of the academic exposition of Dijkstra's Algorithm (such as Wikipedia, or this class page from Darmouth) relies on your priority queue having the ability decrease the key of an entry: the ...
- 193
7
votes
1
answer
322
views
Binary Heap implementation in Common Lisp and tests
I implemented a basic binary heap in Common Lisp to learn programming using the CLOS. It is quite neat and self-contained, the core of the program is about 100 SLOC. The whole repository can be found ...
- 175
4
votes
1
answer
1k
views
Min heap C++ implementation
I have implemented a min heap in C++, and I want to improve it in every possible way. Could you please review it and let me know your suggestions/comments?
...
- 151
5
votes
3
answers
627
views
Repeatedly keep removing 2 smallest elements and add its sum back to the list and return newly inserted elements' total
I have a list of unsorted numbers. Each time, I need to remove 2 smallest numbers and insert back its sum into the list. Repeatedly do this till the 1 final element is remaining in the list.
Return ...
- 151
5
votes
1
answer
182
views
C++11 min-heap with configurable arity
Here is a simple heap implementation that allows the heap arity to be chosen at compile time, including the degenerate case where n=1 and the heap is effectively a sorted array with a terrible repair ...
- 439
1
vote
0
answers
824
views
Max heap in Haskell
I wrote a (max) heap in Haskell which is balanced after every (public) operation. Not based on any documentation. Focus is on:
speed, that is the right time-complexities (not necessarily optimal);
...
- 111
3
votes
0
answers
47
views
Basic Qt5 UI with button [closed]
I have the following Qt class:
mainwindow.h
class MainWindow : public QWidget {
Q_OBJECT
QPushButton* m_button;
public:
explicit MainWindow();
};
mainwindow....
- 203
3
votes
1
answer
105
views
Min Heap Implementation
Min Heap Implementation
As an exercise, I wanted to implement a min heap using JavaScript.
I'm not terribly familiar with JavaScript best practices, so I wanted to get feedback on my approach.
...
- 1,835
3
votes
2
answers
431
views
RFC 1951 "Deflate" compression
This is a little project I did over Christmas, I wanted to understand a bit more about how RFC 1951 (https://www.ietf.org/rfc/rfc1951.txt) compression worked, mostly out of curiosity really. RFC 1951 ...
- 1,246
1
vote
1
answer
56
views
Program to check if heap order is correct or not
There is a Java program to check if a Heap (Min) is in the correct order. Heap Order means the parent is less than both left child and right child.
...
- 145
4
votes
2
answers
114
views
1
vote
2
answers
3k
views
Generic Min Heap Implementation in Java
There is a Min-Heap implementation in Java. BubbleUp() and BubbleDown() could have been coded using recursion but I prefer without recursion. Would there be a major difference if had used recursion? ...
- 145
5
votes
1
answer
189
views
Maximum Heap Container
I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up, bubble_down...
- 541