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.
13
votes
7answers
968 views
Binary Heap where a comparison delegate is used
I currently have a Generic Implementation of a BinaryHeap. It must be able to maintain it's integrity with elements that may or may not implement ...
7
votes
3answers
245 views
Sort Characters By Frequency
I solved this problem.
Problem Statement
Given a string, sort it in decreasing order based on the frequency of
characters.
Example 1
Input: "tree"
Output: "eert"
...
1
vote
1answer
60 views
Template binary heap with lambda function comparator C++
This heap will be used for A* search pathfinding in my 2D isometric game engine. It uses lambda functions (instead of std::less or ...
4
votes
1answer
53 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. ...
5
votes
1answer
92 views
C++ Heap implementation
I'm on my way of understanding basic data structures and sorting algorithms through implementing them in c++. Post is followed of my implementation of Vector. I decided to weld the heap behaviour ...
3
votes
1answer
37 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.
...
4
votes
0answers
136 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.
...
5
votes
2answers
75 views
Continuous median in Ruby
I have written a program in Ruby which calculates the median of a streaming set of numbers dynamically. For each number that arrives, the median is calculated for all the numbers that have arrived so ...
3
votes
1answer
63 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 ...
0
votes
0answers
52 views
Priority Queue/BinaryHeap Implementation in Objective-C
I don't see a ready-made priority queue class in Objective-C. Please review this. Full xcodeproject with unit test cases at https://github.com/smartiothome/BinaryHeap
Heap.h
...
5
votes
1answer
189 views
Indexed Fibonacci heap implementation
I implemented two versions of a Fibonacci heap one using a unordered map (mapping keys to their nodes) so that the client can call decrease in \$O(1)\$ average and ...
0
votes
0answers
30 views
4
votes
2answers
232 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 ...
1
vote
0answers
83 views
Generic Pairing Heap Performance
I have made a generic pairing heap library in C. Pairing heaps are one of the several heap variants with better asymptotic running times than standard binary heaps (others include Fibonacci heaps and ...
3
votes
2answers
232 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, ...
2
votes
1answer
84 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, ...
3
votes
1answer
66 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
2answers
49 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 ...
5
votes
1answer
112 views
A* implementation is not running efficiently but gets correct result
I'm not entirely sure what code other people will need to see, if I miss something off that is important please leave me a comment and I will update it as soon as I possibly can.
I have coded an A* ...
-3
votes
1answer
122 views
Nim Game with Arrays [closed]
I am suppose was to incorporate arrays in my NIM game java code, so that we can allow the user to decide on how many heaps are in play. I am stuck and have no clue how to do so.
Heap Class
...
5
votes
3answers
97 views
Max heap implementation in Kotlin
I wrote this class a while ago to learn Kotlin and heaps, so any tips (on either my code style or my heap algorithm) would be appreciated!
...
1
vote
2answers
668 views
1
vote
0answers
50 views
Generic implementation of mutable binary heap
std::priority_queue does not support dynamically updating element priorities. This class template extends it by allowing updating priorities of elements in the heap....
1
vote
1answer
80 views
Generic implementation of SiftUp/Down operations on binary heap
Binary heap construction and maintenance boil down to the two basic operations: sift up and sift down. Following are generic template implementations of the two operations. Any comments are welcome. I'...
1
vote
2answers
129 views
Fibonacci heap in C - follow-up
(See the previous iteration.)
I have incorporated some points made by ChrisWue and refactored my Fibonacci heap implementation:
fibonacci_heap.h
...
5
votes
3answers
199 views
3
votes
1answer
99 views
Minimalist Tree
While working on a small project, I tried to implement a super simple tree class in C++. It supports an arbitrary number of branches from each node.
In addition to general comments, my main concerns ...
4
votes
0answers
52 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 ...
10
votes
1answer
211 views
Binary heap performance optimization
I have implemented a binary heap as a exercise in data structures. I realize that I'm missing some useful functions (increase/decrease key for example) but I don't consider them interesting for the ...
3
votes
0answers
93 views
Min-Heap based priority queue class written in ES6
I would appreciate any feedback on syntax, naming convention, possible shortcuts, clarity of code and any other constructive feedback. This code was based off of the Priority Queue chapter in The ...
1
vote
2answers
167 views
Read characters from stdin into an resizeable array
As first steps in C, I'm trying to write a program that reads from stdin into an array allocated on the free store, until an exclamation mark ! is entered. The ...
1
vote
0answers
415 views
Min Heap Sort using Generics
Here is my working code for a min-heap sort using an Array-List. I would like any input as to areas that need additional refining and any areas that are against proper formatting/usage. Although not ...
15
votes
1answer
369 views
C# Treap implementation
I recently developed a simple treap data structure in C#. In the future, I may have the class extend IDictionary. For now, I only expose a public accessor and a ...
3
votes
1answer
148 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
73 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 ...
5
votes
2answers
1k views
Merge k Sorted Arrays
Please review my answer for this interview question:
Merge k sorted arrays, using min heap.
...
2
votes
2answers
204 views
Heapsort for arbitrary ranges in Java
I plan to work on Introsort, which requires a working implementation of heap sort. Also, the heap sort implementation must be able to sort arbitrary ranges within an array, which, in turn, requires ...
0
votes
1answer
104 views
Heap selection sort - follow-up
See the previous and initial iteration.
I got rid of Run objects and just maintain two integer arrays in the RunHeap: one for ...
5
votes
1answer
231 views
Heap selection sort in Java
See the next iteration.
I designed and implemented this adaptive heap sort in Java. It works as follows:
Copy the range to be sorted into auxiliary array \$A\$
Create an empty run heap \$H\$
Scan \$...
6
votes
1answer
295 views
D-ary max heap implementation
I implemented a D-ary max heap backed by a vector for resizing. I would like to know any possible improvements in performance, design, and in the code in general.
...
2
votes
1answer
436 views
Sorting an integer array using heap sort
I have written this program to sort an array using heap sort. Please review it for further improvements.
...
-2
votes
1answer
597 views
kth smallest element in min heap [closed]
I am working on to find the kth smallest element in min heap. I have code for this whose complexity is \$O(k \log k)\$. I tried to improve it to \$O(k)\$.
...
8
votes
3answers
363 views
Dijkstra's algorithm without relaxation
I'm trying to implement Dijkstra's algorithm in Python, but the issue is that Python doesn't have support for key-based heaps out of the box, so applying relaxation step of the classical algorithm ...
4
votes
2answers
607 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
4answers
577 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 ...
1
vote
0answers
41 views
Building a correct d-max heap bottom up
I want to implement a d-max heap using a bottom-up approach. This way I will start from the last parent in the tree and build myself up to the root of the heap. We will compare children and parents in ...
1
vote
1answer
292 views
Max-heap implementation with List
I am trying to create max-heap for practice.
Are there any bugs?
Are there ways that I can improve the code quality?
...
8
votes
3answers
3k views
Simple binary heap in C#
I've written a simple binary heap in C# and I want to know if it has any problems or if I can make it better.
...
7
votes
2answers
455 views
Implementation of a binary heap
I've read a little about binary heaps/priority queues and decided to try my hand at making my own implementation of one. I'm not the most experienced programmer and I would be really grateful if you ...
6
votes
2answers
484 views
Function to get top k words in a given String
This is a two-part job:
to identify a word
to find the top k words
I've tried to use regex to split but it's taking 10x more time when string is really long. The ...
