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
2
votes
1answer
938 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
303 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
122 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
478 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
466 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
430 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
221 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
213 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
177 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
606 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
4k views

Array-based MinHeap implementation in Java

This is my implementation of MinHeap in Java. ...
1
vote
1answer
826 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
294 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
135 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
285 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
482 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
85 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
118 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
61 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
503 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
471 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
100 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
363 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
717 views

Binary heap implementation in Golang

I have implemented a binary heap in Go to get familiar with the language. GitHub ...
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
139 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 ...
0
votes
1answer
28 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. ...
0
votes
1answer
46 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 ...
-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)\$. ...
-4
votes
1answer
669 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 ...