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
3
votes
0answers
345 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
133 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
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
576 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, ...
2
votes
1answer
946 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
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 ...
2
votes
1answer
81 views

Optimizing minHeap implementation

I have implemented a java class for minHeap but it is not working as fast as I want . I want some help to change it to work faster in insertion or deleting the minimum node. Here is my implementation:...
2
votes
1answer
64 views

Basic LinkedList implementation [closed]

Please bear in mind, I've only started learning c++ this week, and as such, would love topic suggestions for which I should master, to become better at C++. Below, is my code for a singly linkedlist. ...
2
votes
1answer
349 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 ...
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 ...
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: ...
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. ...
2
votes
2answers
512 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 ...
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. ...
2
votes
1answer
3k views

Fibonacci heap implementation

I'd like this reviewed. ...
2
votes
0answers
34 views

Max Heap Implementation in Python

I decided to challenge myself to code this data structure by just seeing how it looks visually and this is what I got. I can change this easily to minheap by changing some greater than (>) operators. ...
2
votes
0answers
54 views

Fibonacci Heap Implementation In Java

From my repository. This is my first time implementing a Fibonacci Heap, and since it's pretty complicated (at least to me), I would like to check if it is all correct. ...
2
votes
0answers
697 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: ...
2
votes
0answers
452 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
1k views

Generic Min Heap Implementation in Java

There is a Min-Heap implementation in Java. BubbleUp() and BubbleDown() could have been coded using recursion but I prefer without recursion. Would there be a major difference if had used recursion? ...
1
vote
1answer
278 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 ...
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
1answer
31 views

Program to check if heap order is correct or not

There is a Java program to check if a Heap (Min) is in the correct order. Heap Order means the parent is less than both left child and right child. ...
1
vote
1answer
286 views

C++ heap CPS: Continuation Passing Style with Recursion

I am willing to see how to write readable and efficient continuations on the heap in c++. I am not quite satisfied. The following is just an exercise: it is coded for fun. I post the code here ...
1
vote
2answers
681 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 ...
1
vote
2answers
5k views

Array-based MinHeap implementation in Java

This is my implementation of MinHeap in Java. ...
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 ...
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 ...
1
vote
1answer
29 views

Heap selection sort in Javascript

I have (designed and) implemented this fancy sorting algorithm that combines natural runs in the input array with a heap data structure: ...
1
vote
1answer
315 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 ...
1
vote
1answer
525 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. ...
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? ...
1
vote
0answers
26 views

Implement priority queue as min-heap in python

The standard library heapq in python doesn't support updating keys as a public method, which makes it hard to be used as a priority queue. Although the official ...
1
vote
0answers
27 views

Making a priority queue using a Heap. Without using queue or heapq

I have to implement a priority queue using a heap without any library / package for priority queue or heap. I made a BinHeap class which is a min heap, and I made a priority queue class with enqueque, ...
1
vote
0answers
65 views

Binary Heap module in Typescript/Javascript supporting min-heap and max-heap

About binary heaps: https://en.wikipedia.org/wiki/Binary_heap The purpose of this module is to allow quick and efficient priority queue management, compared to linked list. Efficiency: insert: \$O(\...
1
vote
0answers
128 views

Max-Heap Implementation in Kotlin

I am concerned about a few things about my heap implementation. This is in Kotlin. For starters- When and when not to use expressions? The use of also to swap ...
1
vote
0answers
327 views

Max heap in Haskell

I wrote a (max) heap in Haskell which is balanced after every (public) operation. Not based on any documentation. Focus is on: speed, that is the right time-complexities (not necessarily optimal); ...
1
vote
0answers
69 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 ...
1
vote
0answers
568 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. ...
1
vote
0answers
526 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 ...
1
vote
0answers
103 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
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 ...
1
vote
0answers
379 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
0answers
798 views

Binary heap implementation in Golang

I have implemented a binary heap in Go to get familiar with the language. GitHub ...
0
votes
1answer
78 views

My implementation of binary heap

I made my custom heap, that allow to change and delete elements. Please review it and tell me about any found bugs: https://bitbucket.org/nshatokhin/priorityqueue/src/master/ Is this implementation ...
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: ...
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 ...