Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

7
votes
3answers
987 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
91 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: ...
10
votes
0answers
891 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
60 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
2answers
65 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
79 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
157 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
504 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
154 views
1
vote
0answers
35 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
620 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
197 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
100 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
586 views

Fibonacci heap in Python

I have this implementation of the Fibonacci heap in Python: ...
0
votes
0answers
526 views

A priority queue where elements have keys and can adjust element priority by key

This is Python 3 code for a priority queue where elements have keys and can adjust element priority by key. Can I please have this code reviewed? ...
1
vote
1answer
244 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
950 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 ...
0
votes
0answers
248 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
2k 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
439 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
1k 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 ...
10
votes
3answers
712 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
279 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
433 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
3k 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
759 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. ...
3
votes
1answer
518 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
3answers
187 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 ...
0
votes
1answer
40 views

Binary Heap Order Fixing in Java

I am implementing a binary heap in Java. I've come to the point where I have to fix the heap ordering whenever a new node is being inserted to the heap. The code below fixes the heap ordering. I have ...
6
votes
1answer
580 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 ...
7
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 ...
5
votes
1answer
5k 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 ...
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 ...
10
votes
3answers
619 views

My own little memory manager in C

I have implemented a simple version of malloc() and its associated functions, free(), ...
3
votes
0answers
99 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 ...
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 ...
7
votes
3answers
862 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
166 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
485 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
1k 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
133 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
767 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
140 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
161 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 ...
5
votes
3answers
1k 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 ...
4
votes
2answers
1k 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
339 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 ...
4
votes
2answers
3k 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
405 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, ...