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.
136
questions
4
votes
2answers
86 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 ...
4
votes
0answers
63 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 ...
1
vote
0answers
82 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 ...
7
votes
1answer
203 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.
...
3
votes
1answer
90 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 ...
6
votes
3answers
2k views
4
votes
1answer
55 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 ...
4
votes
0answers
37 views
Binary Heap implementation in Common Lisp and tests
I implemented a basic [binary heap] https://en.wikipedia.org/wiki/Binary_heap() in Common Lisp to learn programming using the CLOS. It is quite neat and self-contained, the core of the program is ...
4
votes
1answer
55 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?
...
5
votes
3answers
117 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 ...
5
votes
1answer
140 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 ...
1
vote
0answers
109 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);
...
3
votes
0answers
38 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....
3
votes
1answer
54 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.
...
3
votes
2answers
187 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 ...
0
votes
1answer
28 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.
...
4
votes
2answers
74 views
1
vote
2answers
200 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? ...
5
votes
1answer
167 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...
10
votes
1answer
233 views
Yet Another MinHeap
So, this has been done quite a few times on here, but each of the linked implementations has some significant issues. Since I needed a MinHeap anyway, I figured I would throw my version into the ring.
...
6
votes
1answer
533 views
Python 3 implementation of binary heap
Inspired by exercise on HackerRank where I'm expected to implement binary heap with additional method that allows to remove any value from heap I decided to clean up and expand my code a little. ...
6
votes
2answers
196 views
Binary heap implementation with a generic base class
This is my attempt at implementing a Binary heap. I made an abstract base class Heap with an abstract property controlling whether it is a min-heap or a max-heap.
...
1
vote
1answer
165 views
C++ heap CPS: Continuation Passing Style with Recursion
I am willing to see how to write readable and efficient continuations on the heap in c++. I am not quite satisfied.
The following is just an exercise: it is coded for fun. I post the code here ...
8
votes
4answers
434 views
Binary Heap (list-based)
This is my first attempt at implementing a heap data structure and I've decided to cover the methods Peek, Pop, ...
8
votes
3answers
1k views
Heap implementation for numeric types
I am trying to improve the quality of my code as well as trying to study the Heap data structure. I have implemented a minHeap (Heap in which minimum value nodes ...
2
votes
0answers
441 views
Max Heap Data Structure Implemented with Python List
Created a max heap using a Python list as the base storage. The heap starts at index 1.
Here is the heap:
...
14
votes
1answer
7k views
Min/Max Heap implementation in Python
I'm refreshing some of my datastructures. I saw this as the perfect opportunity to get some feedback on my code.
I'm interested in:
Algorithm wise:
Is my implementation correct? (The tests say so)
...
3
votes
1answer
107 views
Purely functional brodal heap implementation
I implemented the Brodal heap from Brodal & Osaki 1996: Optimal Purely Functional Priority Queues in haskell. The paper gives an implementation in ML but without higher-kinded types. The goal was ...
4
votes
2answers
79 views
Operations on a heap
Introduction
I started going through some basic algorithms as I'll have algorithms course next semester. The last time I've written any heap operations is around 5 years ago. This time around it took ...
3
votes
0answers
203 views
Implementing binary-heap in x86-64 assembly
I'm trying to implement some of the simplest classical data-structures in x86-64 assembly on linux.
PRIMARY GOAL: Reduce memory consumption and increase performance (maybe using x86-64 architecture ...
2
votes
1answer
298 views
Optimisation suggestions for Min Heap
Can someone please optimisations for my implementation of min heap.Its performance is poor compared to the heapq module in python. My use case for the MinHeap class is 'N' insertions and extractions ...
3
votes
2answers
1k views
Binary Heap Implementation in Java
Here's my array-based binary heap java implementation, looking for comments / suggestions on my approach. I used a base heap class to contain most of the logic, since the behavior of min/max heaps is ...
3
votes
1answer
162 views
1
vote
0answers
60 views
Comparing two heap sift algorithms in Java
My research question was to find out whether minimizing the number of assignments in a heap lead to any time savings. The "optimized" version stores the element to sift, sift the minimum to its place ...
2
votes
2answers
2k views
Min&Max Heap implementation in .NET
Overview
I was doing some performance optimization patterns when I stumbled upon PriorityQueue and I implemented for that reason ...
1
vote
1answer
282 views
Binary heap (priority queue) implementation in JavaScript
I wrote this heap implementation because I need it to run Dijkstra's algorithm to find paths in a game (for which reason I'd like this implementation not to be unreasonably slow...)
Sadly I don't ...
3
votes
1answer
143 views
Binary Heap Object
I wrote a basic binary heap object in python 3, and was wondering how it can be improved to be cleaner and more pythonic.
...
5
votes
0answers
947 views
1
vote
1answer
477 views
Template heap/priority-queue data structure with update-key operation
I implemented the following priority-queue/heap with an update-key operation. The update key uses the map from STL, which still requires lg(n) time for lookup. ...
8
votes
1answer
2k views
Prim's Algorithm using heapq module in python
Implementing Prim's with a \$O(m\log n)\$ run time using heaps, similar to Dijkstra heap implementation. Where \$n\$ is the number of nodes, and \$m\$ is the number of edges. Using the ...
1
vote
0answers
497 views
Minimum Priority Queue using Heap
After getting suggestions for Maximum Priority Queue I have written program for Minimum Priority Queue. Help me improve this code.
...
4
votes
2answers
3k views
Maximum Priority Queue using Heap
I have written this program for Maximim Priority Queue after studying from Introduction to Algorithm . I want to improve my code. Is there any other method to implement Priority Queue instead of Heap?
...
1
vote
2answers
591 views
Finding the running median with 2 heaps [closed]
I am trying to solve running median problem in hackerrank https://www.hackerrank.com/challenges/ctci-find-the-running-median and below is my code
...
3
votes
1answer
2k views
C++ Dijkstra's shortest path implementation
I have created a c++ function that searches for the shortest path between two points with dijkstra's shortest path algorithmus. I'm using it right now in combination with a program that solves mazes ...
12
votes
3answers
1k views
Given some integers, return the k most frequent elements
Given a non-empty array of integers, return the k most frequent elements.
For example, given [1,1,1,2,2,3] and k = 2, return <...
3
votes
1answer
461 views
Implementation of the Heap Sort algorithm in C++
I'm writing a little collection of sorting algorithms and some benchmarks (using Google benchmark).
I wrote the following heap sort but I'm struggling in ...
5
votes
2answers
456 views
Select top 2 employees based on Grade and Alphabetical Order
Given a list of Employees ( name and grade). Output the names of the top 2 employees selected for a task(sorted based on grade and then alphabetically).
I am using a maxHeap and override the ...
0
votes
3answers
44 views
Could this be considered a valid mergesort? [closed]
I tried to do a mergesort function for an assignment without importing merge from heapq:
...
6
votes
2answers
6k views
Min & Max heap implementation
As follows I have implemented Min and Max heap data structure, using an array for storing elements. I would need a code review, please.
Please, spare recommendations for generic implementation as they ...
2
votes
2answers
1k views
Binary Min Heap data structure implementation
After reading about heap I tried to implement the heap. Below is my code along with test. Any feedback with respect to correctness, performance is welcome.
...
