blocks|key|3489390|text|使用堆排序二叉树的优先级队列可以使用三重链表结构而不是数组来实现。每个节点需要三个链接:两个向下遍历，一个向上遍历。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3489391|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A priority queue using a heap ordered binary tree can be implemented using a triply linked list structure instead of an array. you will need three links per node:two to traverse down and one to traverse up.

blocks|key|449257|text|heapq+module+source+code显示了实现向上和向下推送的步骤。要从数组实现切换到指针实现，请将arr[2*n%2B1]计算替换为node.left，将arr[2*n%2B2]替换为node.right。对于父引用，如arr[(n-1)>>1]，每个节点都需要一个指向其父节点node.parent的指针。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|449258|或者，您也可以采用函数式风格，这使得这一切都非常容易实现。我发现treaps+implemented+in+Lisp的代码启发了我如何做到这一点。|449259|entityMap|0|LINK|mutability|MUTABLE|url|http://hg.python.org/cpython/file/2.7/Lib/heapq.py|1|http://pavpanchekha.com/programming/treap.html^0|1K|A|1Z|9|2A|A|2N|A|35|D|3Y|B|0|O|0|0|W|Q|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]|$9|U|A|V|B|C]|$9|W|A|X|B|C]|$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@$9|14|A|15|1|16]]|E|$]]|$1|F|3|G|5|6|7|17|8|@]|D|@$9|18|A|19|1|1A]]|E|$]]|$1|H|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]|P|$5|K|L|M|E|$N|Q]]]]

The <a href="http://hg.python.org/cpython/file/2.7/Lib/heapq.py" rel="nofollow">heapq module source code</a> shows to implement the steps for pushing up and down. To switch from an array implementation to a pointer implementation, replace the <code>arr[2*n+1]</code> computation with <code>node.left</code> and <code>arr[2*n+2]</code> with <code>node.right</code>. For parent references such as <code>arr[(n-1)&gt;&gt;1]</code>, every node will need a pointer to its parent, <code>node.parent</code>.

Alternatively, you can adopt a functional style which makes this all very easy to implement. I found the code for <a href="http://pavpanchekha.com/programming/treap.html" rel="nofollow">treaps implemented in Lisp</a> to be an inspiration for how to do this.

blocks|key|2364156|text|作为很久以前的一个任务的一部分，我已经解决了这个问题。你可以在here上找到它|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2364157|我有多个用Java和C%2B%2B实现的实现MinHeap的方法，其中有数组也有数组。有关解决方案，请参阅我的Java实现。是的，在没有数组的情况下实现堆是非常有可能的。您只需记住在何处插入下一个节点，以及如何堆和反堆即可。|2364158|Edit1:我还试图查找没有数组的min+heap的任何现有解决方案，但没有找到任何解决方案。所以，我把它贴在这里，这样对任何想知道方法的人都会有帮助。|2364159|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/hariuserx/MinHeap^0|V|4|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

I have solved this problem as part of an assignment long back. You can find it <a href="https://github.com/hariuserx/MinHeap" rel="nofollow noreferrer">here</a>

I have multiple implementations in Java and C++ implementing MinHeap with and without arrays. See my Java implementations for the solution. And yes it is very much possible to implement Heap without arrays. You just have to remember where to insert the next node and how to heapify and reverse heapify.

Edit1: I also tried to look up any existing solutions for min heap without arrays but couldn't find any. So, I am posting it here so it could be helpful for anyone who wishes to know the approach.

blocks|key|3489553|text|是的，您可以不依赖于数组来实现它。我个人使用的是二进制计数器。这是我在c中的实现(https://github.com/mohamedadnane8/HeapsUsingPointers)。请注意，这仍然是一个使用log(n)的非常快速的实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3489554|++++++++++++++++1+=>+binary+"1"
++++++++++++2=>+"10"++++++++++++3=>+"11"
4=>++"100"++++++5=+"101"+++++6="110"++++++++7="111"|code-block|syntax|javascript|3489555|在这个程序中，我尝试使用数字序列来插入和删除，正如你在上面看到的，树可以很容易地表示为二进制数字字符串。二进制字符串中的第一个“1”是开始。在这之后，0和1的序列决定了去哪里。'1‘表示去左边，'0’去右边。|3489556|此外，请注意，此实现依赖于一个非常小的字符或整数数组，这使得二进制数的计算速度更快，但您可以依靠bin()函数将您的计数器转换为二进制数(我实现该数组只是为了练习一下我的解决问题的技能)。对不起，如果我不能很好地解释它，我缺乏一点沟通技巧。|3489557|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/mohamedadnane8/HeapsUsingPointers^0|15|1G|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|10|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|11|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]]]

Yes, you can implement it without relying on an array.
I personally relied on a binary counter...
Here is my implementation(<a href="https://github.com/mohamedadnane8/HeapsUsingPointers" rel="nofollow noreferrer">https://github.com/mohamedadnane8/HeapsUsingPointers</a>) in c.
Note that this is still a very fast implementation with log(n).
<pre><code> 1 =&gt; binary &quot;1&quot;
 2=&gt; &quot;10&quot; 3=&gt; &quot;11&quot;
4=&gt; &quot;100&quot; 5= &quot;101&quot; 6=&quot;110&quot; 7=&quot;111&quot;
</code></pre>
In this program i tried to use the sequence of numbers to insert and delete as u can see above the tree can be easily represented as binary strings of numbers.
The first '1' in the binary string is to start.
After that the sequence of 0 and 1 determines where to go '1' means go to the left and '0' go to the right.
Also, note that this implementation relies on a very small array of characters or integers that make the calculation of the binary numbers faster but u can rely on bin() function to convert ur counter to a binary number(I implemented the array just to practice a bit my problem-solving skills).
Sorry if I couldn't explain it very well, I lack a bit in my communication skills.

blocks|key|5601222|text|没有数组很难实现二进制堆。因为你应该在插入时保留所有的父级，所以你要传递，然后做向上和向下的操作。喜欢该[parent_1,+parent_2+...+parant_k]+and+then+if+parent_(k%2B1)+<+parant_k+pushUp，并重新排列其右子对象和左子对象|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|5601223|entityMap^0|1G|24|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

It is hard implement binary heap without array. Because you should keep all the parent while inserting you pass and then do operation push up and down. like that <code>[parent_1, parent_2 ... parant_k] and then if parent_(k+1) &lt; parant_k pushUp</code> and rearrange their right child and left child

I found lots of MinMax Heap implementations, that were storing data in an array. It is realy easy to implement, that is way I am looking for something different. I want to create a MinMax Heap using only elements of the Heap with pointers to left child and right child (and afcourse a key to compare). So the Heap have only pointer to the root object (min level), and a root object have a pointer to his children (max level) and so on. I know how to insert a new object (finding a proper path by using binary represenation of int depending on Heap size), but I don't know how to implement the rest (push up (down) the element, find parent or grandparent).

Thx for help

MinMax Heap implementation without an array

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

我发现了许多在数组中存储数据的MinMax堆实现。它真的很容易实现，这就是我寻找不同东西的方式。我想创建一个MinMax堆，只使用堆的元素，指针指向左子和右子(当然还有一个要比较的键)。因此，堆只有指向根对象(最低级别)的指针，而根对象有指向其子对象(最高级别)的指针，依此类推。我知道如何插入一个新对象(根据堆大小，使用int的二进制表示来找到合适的路径)，但我不知道如何实现其余的(向上(向下)元

问不带数组的MinMax堆实现
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不带数组的MinMax堆实现EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不带数组的MinMax堆实现
EN