我正在考虑通过基于属性的测试来测试堆数据结构。看完约翰·休斯之后,我开始测试不变式,即以x为根的任何子树的优先级都比其父级低(使用最小堆)。
到目前为止,我是通过插入一大堆任意数据来设置堆的,但是毕竟,我已经阅读并看到了这种手动的感觉。
有没有一种方法可以使用我的堆insert()
函数在其框架上指定基于堆的值,以插入其提供的任意值?
heap.heap
只是访问堆的基础数组,以便于测试
import * as fc from 'fast-check';
import { Heap } from '../src/Heap';
test('Every sub-root is less than its parent',() => {
fc.assert(
fc.property(fc.array(fc.tuple(fc.string(6),fc.nat())),(a:[string,number][]) => {
let heap:Heap<String> = new Heap();
for (let index = 0; index < a.length; index++) {
const [ val,priority ] = a[index];
heap.insert(val,priority);
}
return heap.heap.every((node,index) => {
let parent = heap[heap.parentIndex(index)];
if (parent != null) {
return node.value < parent.value;
} else {
return true;
}
});
})
)
});