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.

Filter by
Sorted by
Tagged with
5
votes
0answers
958 views

Fibonacci heap in Python

I have this implementation of the Fibonacci heap in Python: ...
4
votes
4answers
15k views

MinHeap implementation in Java

I have made my own MinHeap in Java. I would like to get review comments on the same. ...
4
votes
2answers
2k views

Testing if array is heap

This method tests an array of integers satisfies to see if its a max binary heap. This means each node is greater than or equal to it's children each node has at most 2 children the leaf nodes are ...
4
votes
4answers
1k views

Find Kth largest element in an array

I am preparing for interviews where my code would be judged based on optimizations, OOP concepts, code readability as well as my knowledge of JAVA and design patterns. What comments will you give in ...
4
votes
3answers
294 views

k th smallest element in row wise and column wise sorted matrix

Find the kth smallest element in row wise and column wise sorted element: Example: matrix[row][col] < matrix[row+1][col] matrix[row][col] < matrix[row][col+1] mat= 1 ...
4
votes
2answers
80 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 ...
4
votes
3answers
162 views

Time limit exceeded in Heap

I wrote a Heap, but the judge system reports "time limit exceeded" in some tests. I use a sift_down to build, so I don't know why. Maybe I can improve the build? ...
4
votes
2answers
92 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
2answers
75 views

MaxHeap implementation in JavaScript

Here is MaxHeap implementation in pure JavaScript: ...
4
votes
3answers
15k views

Optimizing Dijkstra implementation using PriorityQueue in Java

I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it ...
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? ...
4
votes
1answer
58 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
1answer
627 views

Find the running median with 2 heaps

I wrote code to solve the running median challenge using 2 heaps, and I'd appreciate any and all feedback. Here is the problem: You have a list of numbers and are scanning them one by one. ...
4
votes
1answer
974 views

Linked list implementation of binary heap insertion

Is this a correct linked list implementation of binary heap insertion? This is not a homework exercise. ...
4
votes
2answers
2k views

Inefficient hash map operation provokes OutOfMemory: Java heap space error

I know I can increase the size of the heap but that seems like a poor solution. This program runs correctly on small files but when run on large data sets it crashes with the OutOfMemory: Java heap ...
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? ...
4
votes
2answers
2k views

Heap implementation of the “median maintenance” algorithm

I have implemented a heap data structure for Coursera's algorithms course. The problem I have to solve is: The goal of this problem is to implement the "Median Maintenance" algorithm. The text ...
4
votes
1answer
421 views

A functional binary heap implementation

I've implemented a binary heap in F#. It's pure and uses zippers for tree modification. To test it out I have implemented heap sort using it but it takes 10 seconds to sort a list of 100 000. Regular ...
4
votes
2answers
3k views

Max heap in Java

I'm just looking for some feedback on my implementation of a maxheap mostly relating to style. I'm trying to create good habits as I learn to program. Note: for the sort method I was given the ...
4
votes
1answer
949 views

Generic min heap in C++

I have recently started programming in C++. I have coded in MATLAB and C in the past. The following code implements a min heap as a generic class in C++. I would like to get some feedback on the ...
4
votes
2answers
5k views

Heap implementation using pointer

I know heaps are commonly implemented by an array. But, I wanted to share my pointer implementation and have your feedback(s) :) General idea: I convert the index to its binary value and then trace ...
4
votes
0answers
68 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 ...
4
votes
0answers
39 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
0answers
128 views

Heap update generic algorithms

In the standard library, there are no algorithms for element updates. This makes it unsuitable as a queue for a Dijkstra's algorithm, for example. Thus I implemented generic heap update functions with ...
4
votes
0answers
642 views

Binomial Heap in Haskell

Here's a partial binomial heap implementation in Haskell (just merge and insert): ...
3
votes
2answers
4k views

Heap Implementation in C#

I am learning fundamental data structures, and I want to know if this is a valid implementation of a heap. Can any C# features be used to improve or extend the implementation? In addition to heapsort, ...
3
votes
2answers
192 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 ...
3
votes
1answer
97 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 ...
3
votes
2answers
144 views

Time Limit Exceeded for build_max_heap

This problem is from HackerEarth: The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an ...
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
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. ...
3
votes
1answer
464 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 ...
3
votes
1answer
51 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 ...
3
votes
1answer
109 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 ...
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 ...
3
votes
1answer
193 views

Efficient bookkeeping in heap

I'm trying to implement a heap using list data structure. I'd also like to keep track of the position of elements in the list in order to enable easy deletion. My implementation involves looping ...
3
votes
1answer
155 views

Heap Sort implementation time complexity

I have implemented Heap sort, but i think the time complexity is more than (nlogn). Could anyone explain me; what is wrong in my code which makes more time complexity. I will be glad if the answer is ...
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
1answer
163 views

A heap class implemetation

...
3
votes
1answer
150 views

Generic Median Heap using PriorityQueues

I've implemented a generic data structure to keep track of the median in a streaming list of numbers. I was hoping to gather the community's feedback on code style and taste. ...
3
votes
1answer
510 views

N-ary heap implementation

NaryHeap as a generalization of binary heap. Each node has up to N children. A template specialization for N = 2 (BinaryHeap) ...
3
votes
1answer
205 views

d-ary heap in C

Now I have this d-ary heap data structure. Note that for d = 2 this is a binary heap. The client programmer specifies the value ...
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
0answers
207 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 ...
3
votes
0answers
121 views

Finding the maximal bottleneck in a 2D matrix from source to destination

I recently started solving programming challenges and this one is causing me performance trouble. The problem statement is the following: You are given a 2d matrix where each cell contains an ...
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 ...
2
votes
1answer
158 views

A different implementation of Heap Sort

The following implementation is a bit different form the standard implementations I have read. Is it correct? ...
2
votes
1answer
3k views

Heap memory preallocation (intended for games)

Currently, in my games, I'm using new and delete to create entities and components. It works fine, but there are slowdowns when ...
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. ...
2
votes
1answer
542 views

(Min)Heap implementation

Being that I needed a min-heap implementation for a project, I implemented one. Now that it's finished I though about having a review for it. I'm interested in all aspects: readability, performance, ...