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
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/...
15
votes
1answer
653 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 ...
14
votes
7answers
1k 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 ...
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 ...
14
votes
1answer
9k 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) ...
13
votes
3answers
5k 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 ...
12
votes
5answers
7k 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. ...
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 <...
11
votes
1answer
622 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 ...
10
votes
3answers
2k views

My own little memory manager in C

I have implemented a simple version of malloc() and its associated functions, free(), ...
10
votes
1answer
249 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. ...
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 ...
8
votes
4answers
442 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 ...
8
votes
3answers
685 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 ...
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? ...
8
votes
1answer
1k views

Python Heap Implementation

I made this snippet for reviewing my DS textbook. Is it okay to write iterative loops in function _upheap and _downheap? Any ...
8
votes
1answer
10k views

Implementing heap in Python

This is basically a straightforward heap implementation. I am just moving from C to Python and I wanted to make sure that I follow Python's best practices in general. This heap is supposed to support ...
8
votes
1answer
3k 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 ...
7
votes
2answers
1k views

C++11 (or C++14?) max heap implementation with a simple example

I've been writing C++03 non-professionally for a long time, and I finally started to play around with C++11 and C++14. I decided to try my hand at implementing a data structure that I was previously ...
7
votes
3answers
1k 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" ...
7
votes
1answer
277 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. ...
7
votes
1answer
54 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 ...
6
votes
3answers
2k views

Huffman Code in C++

This is my version of the Huffman Codes. ...
6
votes
4answers
14k views

MinHeap implementation

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

MaxHeap implementation

I'd like this to be reviewed: ...
6
votes
1answer
2k 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 ...
6
votes
1answer
637 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
1answer
883 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. ...
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. ...
6
votes
1answer
922 views

Sorting almost sorted array with a minimum heap

I'm currently looking into the quickest way to sort an almost sorted array: Given an array of \$n\$ elements, where each element is at most \$k\$ away from its target position, devise an ...
5
votes
2answers
200 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 ...
5
votes
2answers
462 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 ...
5
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 ...
5
votes
1answer
2k views

A* search algorithm: open set and heap

I'm working on an A* search algorithm implemention and this is what I came up with for the open list: ...
5
votes
1answer
171 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...
5
votes
2answers
3k views

Merge k Sorted Arrays

Please review my answer for this interview question: Merge k sorted arrays, using min heap. ...
5
votes
2answers
6k 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...
5
votes
2answers
7k views

Min Heap implementation with Dijkstra's algorithm

I am implementing Dijkstra's Algorithm using Min Heap to speed up the code. For a small number of nodes, the code is really running very fast. But for a large number of nodes, my code is throwing ...
5
votes
3answers
124 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
3answers
2k 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 ...
5
votes
1answer
1k 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 ...
5
votes
1answer
401 views

Tree heap Haskell code

I'd like a review of Haskell tree heap code in Turning a tree into a heap in Haskell. ...
5
votes
1answer
137 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* ...
5
votes
3answers
807 views

Heapsort in Python

Please review the following in-place implementation of Heapsort in Python: ...
5
votes
1answer
54 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 ...