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
1
vote
1answer
1k 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
336 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
840 views

Heapsort in Python

Please review the following in-place implementation of Heapsort in Python: ...
2
votes
1answer
127 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
135 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 ...
11
votes
1answer
672 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 ...
2
votes
0answers
457 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
2k 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
2k 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 ...
16
votes
1answer
734 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
629 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
231 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
3k views

Merge k Sorted Arrays

Please review my answer for this interview question: Merge k sorted arrays, using min heap. ...
2
votes
2answers
522 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
149 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
623 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
979 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
947 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
2k 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
754 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
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
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 ...
1
vote
0answers
381 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
1k 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? ...
12
votes
5answers
8k 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. ...
9
votes
2answers
1k 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
698 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 ...
2
votes
1answer
12k views

Max heap implementation

I have implemented a max-Heap data structure backed by an array. I wanted to know whether this is an acceptable implementation or not. Any improvements or suggestions are welcome. ...
1
vote
0answers
799 views

Binary heap implementation in Golang

I have implemented a binary heap in Go to get familiar with the language. GitHub ...
4
votes
2answers
3k 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 ...
2
votes
1answer
2k views

Binomial heap in Java

I have this implementation of a binomial heap providing insert, decrease-key and extract in logarithmic time. MinPriorityQueue.java: ...
5
votes
1answer
2k views

Binary heap with O(1) lookup and O(log n) change key

I needed a priority queue that allowed efficient searching and changing of keys. I tried std::priority_queue, but the interface was extremely limiting. Not being ...
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? ...
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. ...
14
votes
2answers
1k views

TopCoder problem “Lottery” - SRM 144 (Division I Level Two)

The problem statement Summary: The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that ...
7
votes
4answers
14k views

MinHeap implementation

Please comment on this. ...
6
votes
3answers
17k 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 ...
2
votes
1answer
1k views

Binary HeapSort and Ternary HeapSort implementation

This is my take on binary and ternary heapsort implementation for a university assignment. The code works but I wonder if there are any mistakes or things to improve. ...
1
vote
1answer
139 views

HeapSort Efficiency

For heap (array based) sort, we need to start at index 1, ignoring the 0th index. If I want to make a static function like ...
4
votes
0answers
692 views

Binomial Heap in Haskell

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

Implementation of binary min-heap data structure

What do you think is wrong with this code, and how can it be improved? What corner case have I overlooked, if any? Note: I do not want to use any STL features here, but I'm okay with anything else ...
2
votes
2answers
2k views

Merge N sorted list

Given n sorted lists, merge them. This is a fairly common question, attributed to plenty of interview question websites. I'm looking for code-review, optimizations and best practices. I'm also ...
4
votes
1answer
483 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 ...
6
votes
1answer
1k views

Scala heap implementation

I'm a Scala beginner, so it'd be great if anyone would be so kind to give some feedback. ...
5
votes
2answers
7k views

Constraint Programming: Map color problem

I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor...
15
votes
2answers
18k views

Implementation of binary heap in C++

Things I can think of include integer overflow, if the input type is int, etc. But other than that, what do you think is wrong with this code, design-wise, style-wise, and also in terms of other edge/...
4
votes
3answers
170 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
6k 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 ...
8
votes
1answer
38k views

Implementation of Heap Sort

Is this the correct implementation of Heap Sort using Java? How can it be improved further? ...
6
votes
1answer
4k views

MaxHeap implementation

I'd like this to be reviewed: ...